1.72編輯距離

1.問題描述

找到其中需要進行操作的最少次數。

2.問題轉換

大體思路可以參照前面的兩個字符串的刪除操作。添加操作可以將其看做是一個另類的刪除操作，所以最后全部都可以看做是一個刪除操作

3.解題思路

1. 每一個位置的word1[i]和word2[j]都有兩種狀態：是否相等
2. 如果相等：那么不進行任何操作
3. 如果不相等：那么此時有兩種情況：1.刪除word1[i](也可以是添加word1[i]到word2[j]的位置)。2.刪除word2[j]（也可以看做是添加word2[j]到word1[i]的位置）確定其最小值就是最少操作次數。

4.為什么使用動態規劃？

因為每一個位置的狀態都能由前面的狀態遞推出來

5.動態規劃的具體實現

1. dp[i][j]數組的含義：代表的是從word1[0..i]word2[0..j]最少需要操作的次數保證能夠完全匹配。
2. 遞推公式：

   if(word1[i-1] == word2[j-1]){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = min(dp[i][j-1]+1,dp[i-1][j]+1);}

3. 初始化：for(int i = 0;i<m+1;i++)dp[i][0] = i;for(int j = 1;j<n+1;j++)dp[0][j] = j;因為對于一個是空的字符串，另外一個非空，需要將其全部刪除，所以需要進行如下的初始化
4. 遍歷順序：由遞推公式可以知道，應該是從上到下，從左到右的遍歷順序。

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

2.647回文子串

1.問題描述

找到其中回文子串的數目。回文字符串?是正著讀和倒過來讀一樣的字符串。

2.問題轉換

以i或者i,i+1為中心，向兩邊遍歷，相等則為一個回文子串。

3.解題思路

1. 判斷s[i..j]是否是一個回文串。即判斷s[i]是否和s[j]相等
2. 如果相等：如果里面的長度小于等于1，代表一定是回文串，如果里面的長度大于1的時候，判斷里面是否是回文串，如果是，那么此時是回文串，如果里面不是，那么此時就不是回文串。
3. 如果不相等：那么一定不是回文串

4.為什么使用動態規劃？

因為每一個位置的狀態都能由前面的狀態遞推出來

5.動態規劃的具體實現

1. dp[i][j]數組的含義：代表的是s[i..j]是否是一個回文串。
2. 遞推公式：

   if(s[i]!=s[j]){dp[i][j] = false;}else{if (j - i <= 1) { // 情況一 和 情況二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情況三result++;dp[i][j] = true;}}

3. 初始化：vector<vector<bool>> dp(n,vector<bool>(n,false));默認情況下都不是回文子串，只有i==j的時候默認是回文串，可以在前面初始化，也可以直接在遍歷中設置。
4. 遍歷順序：由遞推公式可以知道，i是從從大到小，j是從小到大，因為i代表左邊界，j代表的是右邊界，如果需要進行擴大的話，是需要向兩端擴的。

class Solution {
public:int countSubstrings(string s) {//第一種方法使用動態規劃的方式來確定回文子串/*int n = s.size();int result = 0;vector<vector<bool>> dp(n,vector<bool>(n,false));//代表的是表示區間范圍[i,j] （注意是左閉右閉）的子串是否是回文子串，如果是dp[i][j]為true，否則為false。for(int i = n-1;i>=0;i--){for(int j = i;j<n;j++){if(s[i]!=s[j]){dp[i][j] = false;}else{if (j - i <= 1) { // 情況一 和 情況二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情況三result++;dp[i][j] = true;}}}}return result;*///第二種方式：使用二分法int n = s.size();int res = 0;for(int i = 0; i < n; ++i){for(int j = i, k = i; j >=0 && k < n; --j,++k)//以i為中心有多少個回文子串{if(s[j] != s[k]) break;++res;}for(int j = i, k = i+1; j >=0 && k < n; --j,++k)//以i,i+1兩個為整體有多少個回文子串{if(s[j] != s[k]) break;++res;}}return res;}
};

3.516最長回文子序列

1.問題描述

找到其中最長的回文子串的長度。

2.問題轉換

從[i..j]之間中最長的回文子串，只需要找到相同的就代表長度+2.

3.解題思路

1. 求解s[i..j]最長回文子串的長度。即判斷s[i]是否和s[j]相等
2. 如果相等：長度+2
3. 如果不相等：那么在s[i+1..j]或者s[i..j-1]中找到最長的回文子串作為此時的長度

4.為什么使用動態規劃？

因為每一個位置的狀態都能由前面的狀態遞推出來

5.動態規劃的具體實現

1. dp[i][j]數組的含義：代表的是s[i..j]的最長回文子串的長度。
2. 遞推公式：

   if(s[i] == s[j]){dp[i][j] = dp[i+1][j-1]+2;}else{dp[i][j] = max(dp[i+1][j],dp[i][j-1]);}

3. 初始化：for(int i = 0;i<n;i++){//因為單個字符也是回文子序列dp[i][i] = 1;}
4. 遍歷順序：由遞推公式可以知道，i是從從大到小，j是從小到大，因為i代表左邊界，j代表的是右邊界，如果需要進行擴大的話，是需要向兩端擴的。

class Solution {
public:int longestPalindromeSubseq(string s) {int n = s.size();vector<vector<int>> dp(n,vector<int>(n,0));//dp[i][j]:s[i,j]數組的最長的回文子序列for(int i = 0;i<n;i++){//因為單個字符也是回文子序列dp[i][i] = 1;}for(int i = n-2;i>=0;i--){//由于dp[i][j] = max(dp[i+1][j],dp[i][j-1]);所以i是從從大到小，j是從小到大，遞推for(int j = i+1;j<n;j++){if(s[i] == s[j]){dp[i][j] = dp[i+1][j-1]+2;}else{dp[i][j] = max(dp[i+1][j],dp[i][j-1]);}}}return dp[0][n-1];}
};