【动态规划篇】最少分割回文 编辑距离 不同的子序列
🌠作者：@阿亮joy.
🎆专栏：《数据结构与算法要啸着学》
🎇座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根
目录
- 👉最少分割回文👈
- 👉编辑距离👈
- 👉不同的子序列👈
- 👉总结👈
👉最少分割回文👈
给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的最少分割次数 。
思路：
class Solution
{
private:
bool isPalindrome(const string& s, int begin, int end)
{
while(begin < end)
{
if(s[begin] != s[end])
{
return false;
}
++begin;
--end;
}
return true;
}
public:
int minCut(string s)
{
int len = s.size();
vector<int> minCut(len + 1);
// 初始状态：F(i) = i - 1
for(int i = 1; i <= len; ++i)
{
minCut[i] = i - 1;
}
for(int i = 2; i <= len; ++i)
{
// [1, i]整体是回文串
if(isPalindrome(s, 0, i - 1))
{
minCut[i] = 0;
continue;
}
// j < i && [j + 1, i]是否为回文串
for(int j = 1; j < i; ++j)
{
if(isPalindrome(s, j, i - 1))
{
minCut[i] = min(minCut[i], minCut[j] + 1);
}
}
}
return minCut[len];
}
};
class Solution
{
private:
bool isPalindrome(const string& s, int begin, int end)
{
while(begin < end)
{
if(s[begin] != s[end])
{
return false;
}
++begin;
--end;
}
return true;
}
public:
int minCut(string s)
{
int len = s.size();
vector<int> minCut(len + 1);
// 初始状态：F(i) = i - 1
for(int i = 0; i <= len; ++i)
{
minCut[i] = i - 1;
}
// F(0) = -1，若整个字符串为回文串，也能得出最小分割次数为0
for(int i = 2; i <= len; ++i)
{
// j < i && [j + 1, i]是否为回文串
for(int j = 0; j < i; ++j)
{
if(isPalindrome(s, j, i - 1))
{
minCut[i] = min(minCut[i], minCut[j] + 1);
}
}
}
return minCut[len];
}
};
上面的解法是 O(N ^ 3) 的算法，两层 for 循环再加一个判断回文串 O(N) 的算法，所以这个解法的时间复杂度为 O(N ^ 3)。我们可以先将回文串的结果保存下来，要用时可以直接用，这样就可以将时间复杂度将到 O(N ^ 2) 了。
判断回文串也是需要用到动态规划的。
class Solution
{
private:
vector<vector<bool>> getMat(const string& s)
{
int n = s.size();
vector<vector<bool>> Mat(n, vector<bool>(n, false));
// 从矩阵的右下角开始更新
for(int i = n - 1; i >= 0; --i)
{
for(int j = i; j < n; ++j)
{
if(j == i) // 初始状态
Mat[i][j] = true;
else if(j == i + 1)
Mat[i][j] = s[i] == s[j];
else
Mat[i][j] = ((s[i] == s[j]) && (Mat[i + 1][j - 1]));
}
}
return Mat;
}
public:
int minCut(string s)
{
int len = s.size();
vector<vector<bool>> Mat = getMat(s);
vector<int> minCut(len + 1);
// 初始状态：F(i) = i - 1
for(int i = 0; i <= len; ++i)
{
minCut[i] = i - 1;
}
// F(0) = -1，若整个字符串为回文串，也能得出最小分割次数为0
for(int i = 2; i <= len; ++i)
{
// j < i && [j + 1, i]是否为回文串
for(int j = 0; j < i; ++j)
{
if(Mat[j][i - 1])
{
minCut[i] = min(minCut[i], minCut[j] + 1);
}
}
}
return minCut[len];
}
};
该解法的时间复杂度为 O(N ^ 2)，空间复杂度为 O(N ^ 2)，典型的以空间换时间的做法。
👉编辑距离👈
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
思路：
class Solution
{
public:
int minDistance(string word1, string word2)
{
int row = word1.size();
int col = word2.size();
vector<vector<int>> minEdit(row + 1, vector<int>(col + 1));
// 初始状态：F(i, 0) = 0 和 F(0, j) = j
for(int i = 0; i <= row; ++i) minEdit[i][0] = i;
for(int j = 1; j <= col; ++j) minEdit[0][j] = j;
for(int i = 1; i <= row; ++i)
{
for(int j = 1; j <= col; ++j)
{
// 插入和删除
minEdit[i][j] = min(minEdit[i][j - 1], minEdit[i - 1][j]) + 1;
// 替换 word1[i - 1]是否等于word2[j - 1]
if(word1[i - 1] == word2[j - 1])
{
minEdit[i][j] = min(minEdit[i][j], minEdit[i - 1][j - 1]);
}
else
{
minEdit[i][j] = min(minEdit[i][j], minEdit[i - 1][j - 1] + 1);
}
}
}
return minEdit[row][col];
}
};
👉不同的子序列👈
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）
题目数据保证答案符合 32 位带符号整数范围。
思路：
class Solution
{
public:
int numDistinct(string s, string t)
{
int row = s.size();
int col = t.size();
vector<vector<unsigned int>> dp(row + 1, vector<unsigned int>(col + 1, 0));
for(int i = 0; i <= row; ++i) dp[i][0] = 1; // 初始状态
for(int i = 1; i <= row; ++i)
{
for(int j = 1; j <= col; ++j)
{
if(s[i - 1] == t[j - 1])
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[row][col];
}
};
空间复杂度优化
由于当前的dp[i][j]仅取决于dp[i - 1][j - 1]和dp[i - 1][j]，所以我们不需要用二维数组将所有状态的解都保留下来，可以用一维数组将上一次的解保留下来就行了。但需要注意的是，需要从后向前更新，不然无法拿到上一次的解。
class Solution
{
public:
int numDistinct(string s, string t)
{
int row = s.size();
int col = t.size();
// 初始状态
vector<unsigned int> dp(col + 1, 0);
dp[0] = 1;
for(int i = 1; i <= row; ++i)
{
for(int j = col; j >= 1; --j)
{
if(s[i - 1] == t[j - 1])
dp[j] = dp[j - 1] + dp[j]; // dp += dp[i - 1]
// s[i - 1] != t[j - 1]时，不需要更新dp[j]
}
}
return dp[col];
}
};
👉总结👈
动态规划的难点：
- 状态如何定义：从问题中抽象出状态，每一个状态都对应着一个子问题。状态的定义可能不止一种方式，那如何定义状态的合理性呢？某一个状态的阶或者多个状态的解能否推出最终问题的解，也就是状态之间能够形成递推关系（状态转移方程）。
- 一维状态 VS 二维状态：首先尝试一维状态，如果一维状态的合理性不满足时，再去尝试二维状态。
- 常见问题的状态：字符串：状态一般对应子串，状态一般每次增加一个新的字符。二维状态有时候能够优化成一维状态。
那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️