1.72编辑距离
1.问题描述
找到其中需要进行操作的最少次数。
2.问题转换
大体思路可以参照前面的两个字符串的删除操作。添加操作可以将其看做是一个另类的删除操作，所以最后全部都可以看做是一个删除操作
3.解题思路
- 每一个位置的word1[i]和word2[j]都有两种状态：是否相等
- 如果相等：那么不进行任何操作
- 如果不相等：那么此时有两种情况：1.删除word1[i](也可以是添加word1[i]到word2[j]的位置)。2.删除word2[j]（也可以看做是添加word2[j]到word1[i]的位置）确定其最小值就是最少操作次数。
4.为什么使用动态规划？
因为每一个位置的状态都能由前面的状态递推出来
5.动态规划的具体实现
- dp[i][j]数组的含义：代表的是从word1[0..i]word2[0..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]+1,dp[i-1][j]+1); } - 初始化：for(int i = 0;i<m+1;i++)dp[i][0] = i;for(int j = 1;j<n+1;j++)dp[0][j] = j;因为对于一个是空的字符串，另外一个非空，需要将其全部删除，所以需要进行如下的初始化
- 遍历顺序：由递推公式可以知道，应该是从上到下，从左到右的遍历顺序。
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.解题思路
- 判断s[i..j]是否是一个回文串。即判断s[i]是否和s[j]相等
- 如果相等：如果里面的长度小于等于1，代表一定是回文串，如果里面的长度大于1的时候，判断里面是否是回文串，如果是，那么此时是回文串，如果里面不是，那么此时就不是回文串。
- 如果不相等：那么一定不是回文串
4.为什么使用动态规划？
因为每一个位置的状态都能由前面的状态递推出来
5.动态规划的具体实现
- dp[i][j]数组的含义：代表的是s[i..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; } } - 初始化：vector<vector<bool>> dp(n,vector<bool>(n,false));默认情况下都不是回文子串，只有i==j的时候默认是回文串，可以在前面初始化，也可以直接在遍历中设置。
- 遍历顺序：由递推公式可以知道，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.解题思路
- 求解s[i..j]最长回文子串的长度。即判断s[i]是否和s[j]相等
- 如果相等：长度+2
- 如果不相等：那么在s[i+1..j]或者s[i..j-1]中找到最长的回文子串作为此时的长度
4.为什么使用动态规划？
因为每一个位置的状态都能由前面的状态递推出来
5.动态规划的具体实现
- dp[i][j]数组的含义：代表的是s[i..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]); } - 初始化：for(int i = 0;i<n;i++){//因为单个字符也是回文子序列dp[i][i] = 1;}
- 遍历顺序：由递推公式可以知道，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];
}
};