👉最少分割回文👈
给定一个字符串 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 二维状态：首先尝试一维状态，如果一维状态的合理性不满足时，再去尝试二维状态。
常见问题的状态：字符串：状态一般对应子串，状态一般每次增加一个新的字符。二维状态有时候能够优化成一维状态。
那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
