【算法】动态规划：回文子串问题、两个数组的dp
目录
回文子串问题
回文子串
- 回文子串
定义 dp[i][j] 表示以i位置元素为头，j位置元素为尾的回文子串，i <= j，要特别注意填表顺序。
class Solution {
public:int countSubstrings(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n));int ret = 0;for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){if (s[i] == s[j])dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;if (dp[i][j]) ret++;}}return ret;}
};
最长回文子串
- 最长回文子串
一边填dp表，一边统计最长的回文子串。
class Solution {
public:string longestPalindrome(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n));int begin = 0, len = 1;for (int i = n - 1; i >= 0; i--)for (int j = i; j < n; j++){if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;if (dp[i][j] && j - i + 1 > len) {len = j - i + 1;begin = i;}}return s.substr(begin, len);}
};
分割回文串 IV
- 分割回文串 IV
class Solution {
public:bool checkPartitioning(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n));for (int i = n - 1; i >= 0; i--)for (int j = i; j < n; j++)if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;for (int i = 0; i < n - 1; i++)for (int j = 0; j < n - 1; j++)if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1])return true;return false;}
};
分割回文串 II *
- 分割回文串 II
定义状态 dp[i] 表示0-i区间符合要求的最少分割次数。
如果 j - i 是回文子串，则 dp[i] = dp[j - 1] + 1；后面的+1表示分割一次。
class Solution {
public:int minCut(string s) {int n = s.size();vector<vector<bool>> isPal(n, vector<bool>(n));for (int i = n - 1; i >= 0; i--)for (int j = i; j < n; j++)if (s[i] == s[j]) isPal[i][j] = i + 1 < j ? isPal[i + 1][j - 1] : true;vector<int> dp(n, INT_MAX);for (int i = 0; i < n; i++){if (isPal[0][i]) dp[i] = 0;else{for (int j = 1; j <= i; j++)if (isPal[j][i])dp[i] = min(dp[j - 1] + 1, dp[i]);}}return dp[n - 1];}
};
最长回文子序列
- 最长回文子序列
定义状态 dp[i][j] 表示区间 i到j 范围内的所有子序列中，最长回文子序列的长度。
当首尾两个元素「相同」的时候，也就是s[i] == s[j] ：那么[i, j] 区间上的最长回文子序列，应该是[i + 1, j - 1] 区间内的那个最长回文子序列首尾填上s[i] 和s[j] ，此时dp[i][j] = dp[i + 1][j - 1] + 2.
当 s[i] != s[j] 时： dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])。
class Solution {
public:int longestPalindromeSubseq(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int>(n));for (int i = n - 1; i >= 0; i--){dp[i][i] = 1;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][j - 1], dp[i + 1][j]);}}return dp[0][n - 1];}
};
让字符串成为回文串的最少插入次数
- 让字符串成为回文串的最少插入次数
定义状态 dp[i][j] 表示让i到j区间称为回文串的最小插入次数。
i == j 时不用考虑，在初始化dp表的时候其中的值默认为0，所以直接在 j = i + 1 处开始遍历；i + 1 == j 可以放在 i + 1 < j 中，因为 dp[i + 1][j - 1] 访问的是 i + 1 == j 的左下角，这个位置刚好用不到，默认也为0。
当 s[i] != s[j] 时，我们假定在i的左边插入一个s[j]，或在j的右边插入一个s[i]，然后就可以在 dp[i][j - 1] 或 dp[i + 1][j] 中找最小操作次数。
class Solution {
public:int minInsertions(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int>(n));for (int i = n - 1; i >= 0; i--){for (int j = i + 1; j < n; j++)if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];else dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;}return dp[0][n - 1];}
};
两个数组的dp
最长公共子序列
- 最长公共子序列
定义状态 dp[i][j] 为s1的[0, i]区间和s2的[0, j]区间中所有的子序列中，最长公共子序列的长度。
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){if (text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return dp[m][n];}
};
不相交的线
- 不相交的线
说白了我白说了，这就是 “最长公共子序列”。
我是程序猿，我可以作证，代码一模一样。
class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size(), n = nums2.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){if (nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return dp[m][n];}
};
不同的子序列
- 不同的子序列
dp[i][j]表示s的[0, j]区间中所有的子序列中有多少个t的[0, j]区间的子串。
class Solution {
public:int numDistinct(string s, string t) {const int mod = 1e9 + 7;int m = t.size(), n = s.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for (int i = 0; i < n; i++) dp[0][i] = 1;for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){dp[i][j] = dp[i][j - 1];if (s[j - 1] == t[i - 1])dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;}}return dp[m][n];}
};
通配符匹配 *
- 通配符匹配
dp[i][j] 表示 p[0, j] 内的子串能否匹配 s[0, i] 内的子串。
class Solution {
public:bool isMatch(string s, string p) {int m = s.size(), n = p.size();// 对应下标s = ' ' + s;p = ' ' + p;vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));// 初始化空串的情况dp[0][0] = true;for (int i = 1; i <= n; i++)if (p[i] == '*') dp[0][i] = true;else break;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)if (p[j] == '*') dp[i][j] = dp[i - 1][j] || dp[i][j - 1];else dp[i][j] = (p[j] == '?' || s[i] == p[j]) && dp[i - 1][j - 1];return dp[m][n];}
};
正则表达式匹配
- 正则表达式匹配
定义状态 dp[i][j] 表示 p[0, j] 区间内的子串能否匹配 s[0, i] 区间内的子串。
class Solution {
public:bool isMatch(string s, string p) {int m = s.size(), n = p.size();// 对应下标s = ' ' + s;p = ' ' + p;vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));// 初始化空串的情况dp[0][0] = true;for (int i = 2; i <= n; i += 2)if (p[i] == '*') dp[0][i] = true;else break;for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){if (p[j] == '*') dp[i][j] = dp[i][j-2] || ((s[i] == p[j-1] || p[j-1] == '.') && dp[i-1][j]);elsedp[i][j] = (s[i] == p[j] || p[j] == '.') && dp[i-1][j-1];}}return dp[m][n];}
};
交错字符串
- 交错字符串
定义状态 dp[i, j] 表示 s1[0, i] 区间内的字符串和 s2[0, j] 区间内的字符串能否拼接成 s3[0, i + j] 区间内的字符串。
class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int m = s1.size(), n = s2.size();if (m + n != s3.size()) return false;s1 = ' ' + s1, s2 = ' ' + s2, s3 = ' ' + s3;vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));dp[0][0] = true;for (int i = 1; i <= n; i++)if (s2[i] == s3[i]) dp[0][i] = true;else break;for (int i = 0; i <= m; i++)if (s1[i] == s3[i]) dp[i][0] = true;else break;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]) || (s2[j] == s3[i + j] && dp[i][j - 1]);return dp[m][n];}
};
本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
