算法學(xué)習(xí)——LeetCode力扣動態(tài)規(guī)劃篇10

583. 兩個字符串的刪除操作

583. 兩個字符串的刪除操作 - 力扣（LeetCode）

描述

給定兩個單詞 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步數(shù)。

每步 可以刪除任意一個字符串中的一個字符。

示例

示例 1：

輸入: word1 = “sea”, word2 = “eat”
輸出: 2
解釋: 第一步將 “sea” 變?yōu)?“ea” ，第二步將 "eat "變?yōu)?“ea”

示例 2:

輸入：word1 = “l(fā)eetcode”, word2 = “etco”
輸出：4

提示

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小寫英文字母

代碼解析

動態(tài)規(guī)劃

和1143相同，只要求出兩個字符串的最長公共子序列長度即可，那么除了最長公共子序列之外的字符都是必須刪除的，最后用兩個字符串的總長度減去兩個最長公共子序列的長度就是刪除的最少步數(shù)。

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1 , vector<int>(word2.size()+1 ,0));for(int i=0 ;i<word1.size() ;i++){for(int j=0 ;j<word2.size() ;j++){if(word1[i] == word2[j]) dp[i+1][j+1] = dp[i][j] + 1;else dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);}}return word1.size() + word2.size() - 2*dp[word1.size()][word2.size()];}
};

72. 編輯距離

72. 編輯距離 - 力扣（LeetCode）

描述

給你兩個單詞 word1 和 word2， 請返回將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。

你可以對一個單詞進(jìn)行如下三種操作：

插入一個字符
刪除一個字符
替換一個字符

示例

示例 1：

輸入：word1 = “horse”, word2 = “ros”
輸出：3
解釋：
horse -> rorse (將 ‘h’ 替換為 ‘r’)
rorse -> rose (刪除 ‘r’)
rose -> ros (刪除 ‘e’)

示例 2：

輸入：word1 = “intention”, word2 = “execution”
輸出：5
解釋：
intention -> inention (刪除 ‘t’)
inention -> enention (將 ‘i’ 替換為 ‘e’)
enention -> exention (將 ‘n’ 替換為 ‘x’)
exention -> exection (將 ‘n’ 替換為 ‘c’)
exection -> execution (插入 ‘u’)

提示

0 <= word1.length, word2.length <= 500
word1 和 word2 由小寫英文字母組成

代碼解析

動態(tài)規(guī)劃

• 確定dp數(shù)組以及下標(biāo)的含義
  dp[i][j] 表示前 i 個字符的word1，和前 j 個字符的word2，最近編輯距離。
• 遞推公式
  • if (word1[ i ] == word2[ j ]) 那么說明不用任何編輯，
    即dp[i+1][j+1] = dp[i ][j ];
  • if (word1[ i ] ！= word2[ j ]) 有三種情況
    • 刪除world1
      word1第 i 個字符刪除一個元素，就是world1第 i -1 與world2第 j 再加上一個操作。
      即 dp[i+1][j+1] = dp[ i ][ j+1] + 1;
    • 刪除world2（相當(dāng)于添加world1）
      word2第 j 個字符刪除一個元素，就是world1第 i 與world2第 j -1 再加上一個操作。
      即 dp[i+1][j+1] = dp[ i +1][ j] + 1;
    • 替換元素
      word1第 i 個字符和word1第 i -1個字符替換，world2同樣，就是world1第 i -1 與world2第 j -1 再加上一個操作。
      即 dp[i+1][j+1] = dp[ i ][ j] + 1;
    • 最終三種情況取最小
      dp[i+1][j+1] = min( dp[i][j] , min(dp[i][j+1],dp[i+1][j])) + 1;
• dp數(shù)組初始化

  • dp[i][0] ：以下標(biāo)i-1為結(jié)尾的字符串word1，和空字符串word2，最近編輯距離為dp[i][0]。
    那么dp[i][0]就應(yīng)該是i，對word1里的元素全部做刪除操作，即：dp[i][0] = i;

  • 同理dp[0][j] = j;
    
    

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1 , vector<int>(word2.size()+1));for(int i=0 ; i<word1.size();i++)dp[i+1][0] = i+1;for(int j=0 ; j<word2.size();j++)dp[0][j+1] = j+1;for(int i=0;i<word1.size();i++){for(int j=0; j<word2.size();j++){if(word1[i] == word2[j]) dp[i+1][j+1] = dp[i][j];else dp[i+1][j+1] = min( dp[i][j] , min(dp[i][j+1],dp[i+1][j])) + 1;}}return dp[word1.size()][word2.size()];}
};

647. 回文子串

647. 回文子串 - 力扣（LeetCode）

描述

給你一個字符串 s ，請你統(tǒng)計并返回這個字符串中 回文子串 的數(shù)目。

回文字符串 是正著讀和倒過來讀一樣的字符串。

子字符串 是字符串中的由連續(xù)字符組成的一個序列。

具有不同開始位置或結(jié)束位置的子串，即使是由相同的字符組成，也會被視作不同的子串。

示例

示例 1：

輸入：s = “abc”
輸出：3
解釋：三個回文子串: “a”, “b”, “c”

示例 2：

輸入：s = “aaa”
輸出：6
解釋：6個回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示

1 <= s.length <= 1000
s 由小寫英文字母組成

代碼解析

暴力法

class Solution {
public:bool cheak(const string s , int left,int right){for(int i=left ,j=right; i<=(right-left)/2 +left; i++,j--){if(s[i]!=s[j]) return false;}return true;}int countSubstrings(string s) {if(s.size()<=1) return 1;int num=0;int left=0,right=1;for(int left=0 ; left<s.size() ;left++){for(right=left ; right<s.size();right++){if(cheak(s,left,right)==1){num++;// cout<<left<<' '<<right<<endl;}}}return num;}
};

動態(tài)規(guī)劃

• 確定dp數(shù)組（dp table）以及下標(biāo)的含義
  布爾類型的dp[i][j]：表示區(qū)間范圍[i,j] （注意是左閉右閉）的子串是否是回文子串，如果是dp[i][j]為true，否則為false。

• 確定遞推公式
  在確定遞推公式時，就要分析如下幾種情況。

  • 當(dāng)s[i]與s[j]不相等，那沒啥好說的了，dp[i][j]一定是false。

  • 當(dāng)s[i]與s[j]相等時，這就復(fù)雜一些了，有如下三種情況
    情況一：下標(biāo)i 與 j相同，同一個字符例如a，當(dāng)然是回文子串
    情況二：下標(biāo)i 與 j相差為1，例如aa，也是回文子串
    情況三：下標(biāo)：i 與 j相差大于1的時候，例如cabac，此時s[i]與s[j]已經(jīng)相同了，我們看i到j(luò)區(qū)間是不是回文子串就看aba是不是回文就可以了，那么aba的區(qū)間就是 i+1 與 j-1區(qū)間，這個區(qū)間是不是回文就看dp[i + 1][j - 1]是否為true。

• dp數(shù)組如何初始化
  dp[i][j]可以初始化為true么？ 當(dāng)然不行，怎能剛開始就全都匹配上了。
  所以dp[i][j]初始化為false。

• 確定遍歷順序
  遍歷順序可有有點講究了。
  首先從遞推公式中可以看出，情況三是根據(jù)dp[i + 1][j - 1]是否為true，在對dp[i][j]進(jìn)行賦值true的。
  dp[i + 1][j - 1] 在 dp[i][j]的左下角，
  一定要從下到上，從左到右遍歷，這樣保證dp[i + 1][j - 1]都是經(jīng)過計算的。
  因為dp[i][j]的定義，所以j一定是大于等于i的，那么在填充dp[i][j]的時候一定是只填充右上半部分。
  

class Solution {
public:int countSubstrings(string s) {if(s.size()<=1) return 1;vector<vector<bool>> dp(s.size(),vector<bool>(s.size() , false));int num = 0;for(int i=s.size()-1 ; i>=0;i--)for(int j=i ;j<s.size();j++)//s[i]==s[j]為首尾相同//并且j-i <= 1為"a"或者"aa"的情況,為回文串//如果j-i不是<=1,但是dp[i+1][j-1]==true，也是回文串，因為首位相同中間是回文串//如dabcd，首位d相同，中間dp[i+1][j-1]為abc也是回文串，即dabcd為回文串if(  s[i]==s[j] &&(j-i <= 1||dp[i+1][j-1]==true)  )  {num++;dp[i][j] = true;}return num;}
};

516. 最長回文子序列

516. 最長回文子序列 - 力扣（LeetCode）

描述

給你一個字符串 s ，找出其中最長的回文子序列，并返回該序列的長度。

子序列定義為：不改變剩余字符順序的情況下，刪除某些字符或者不刪除任何字符形成的一個序列。

示例

示例 1：

輸入：s = “bbbab”
輸出：4
解釋：一個可能的最長回文子序列為 “bbbb” 。

示例 2：

輸入：s = “cbbd”
輸出：2
解釋：一個可能的最長回文子序列為 “bb” 。

提示

1 <= s.length <= 1000
s 僅由小寫英文字母組成

代碼解析

動態(tài)規(guī)劃

• 確定dp數(shù)組（dp table）以及下標(biāo)的含義
  dp[i][j]：字符串s在[i, j]范圍內(nèi)最長的回文子序列的長度為dp[i][j]。

• 確定遞推公式
  在判斷回文子串的題目中，關(guān)鍵邏輯就是看s[i]與s[j]是否相同。

  • 如果s[i]與s[j]相同，
    • j - i ==0 , dp[i][j] = 1;
    • j - i == 1, dp[i][j] = 2;
    • j - i > 2, dp[i][j] = dp[i + 1][j - 1] + 2;
      
  • 如果s[i]與s[j]不同
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

• 確定遍歷順序
  從遞推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 可以看出，dp[i][j]是依賴于dp[i + 1][j - 1] 和 dp[i + 1][j]，
  也就是從矩陣的角度來說，dp[i][j] 下一行的數(shù)據(jù)。 所以遍歷i的時候一定要從下到上遍歷，這樣才能保證，下一行的數(shù)據(jù)是經(jīng)過計算的。
  

class Solution {
public:int longestPalindromeSubseq(string s) {if(s.size()<=1) return s.size();vector<vector<int>> dp(s.size() , vector<int>(s.size() ,0));int result = 0;for(int i=s.size()-1; i>=0 ;i-- )for(int j=i ;j<s.size();j++){if(s[i]==s[j]){if(j==i) dp[i][j] = 1;else if(j-i==1) dp[i][j] = 2;else dp[i][j] = dp[i+1][j-1] + 2;if(dp[i][j] > result) result = dp[i][j];}else{dp[i][j] = max(dp[i][j-1],dp[i+1][j]);}}// for(int i=0;i<s.size();i++)// {//     for(int j=0;j<s.size();j++)//     cout<<dp[i][j]<<' ';//     cout<<endl;// }return result;}
};