第九章 动态规划 part13
今天我们就要结束动态规划章节了，大家激不激动！！！
详细布置
647. 回文子串
动态规划解决的经典题目，如果没接触过的话，别硬想，直接看题解。
647. 回文子串
看似很难，实际上确实挺难。
我们将使用输入字符串 s = "aba" 来填充 dp 数组，并展示其每个元素的值。
好的，下面我们来展示字符串 s = "abab" 的三乘三 dp 数组。
对于字符串 s = "abab"，我们会通过填充 dp 数组来表示不同子串是否为回文。
填充 dp 数组过程
我们根据判断子串是否为回文，逐步填充 dp 数组：
i=3, j=3：子串"b"，单字符总是回文，dp[3][3] = 1。i=2, j=2：子串"a"，单字符总是回文，dp[2][2] = 1。i=2, j=3：子串"ab"，s[2] != s[3]，不是回文，dp[2][3] = 0。i=1, j=1：子串"b"，单字符总是回文，dp[1][1] = 1。i=1, j=2：子串"ba"，s[1] != s[2]，不是回文，dp[1][2] = 0。i=1, j=3：子串"bab"，s[1] == s[3]且子串dp[2][2] = 1（即"a"是回文），因此dp[1][3] = 1。i=0, j=0：子串"a"，单字符总是回文，dp[0][0] = 1。i=0, j=1：子串"ab"，s[0] != s[1]，不是回文，dp[0][1] = 0。i=0, j=2：子串"aba"，s[0] == s[2]且子串dp[1][1] = 1（即"b"是回文），因此dp[0][2] = 1。i=0, j=3：子串"abab"，s[0] != s[3]，不是回文，dp[0][3] = 0。
最终 dp 数组
总结
最终 dp 数组表示了字符串 s 中各个子串的回文状态，1 表示回文，0 表示非回文。
class Solution {
public:
int countSubstrings(string s) {
int count = 0;
vector<vector<int>> dp(s.size() , vector<int>(s.size() , 0));
for (int i = s.size()-1; i >=0; i--) {
for (int j = i; j < s.size(); j++) {
if (s[i ] == s[j ]) {
if ( j-i <= 1) {
count++;
dp[i][j] = 1;
}
else if (dp[i + 1][j - 1]) { // 情况三
count++;
dp[i][j] = 1;
}
}
}
}
return count;
}
};
难度还是有些的，多按照上面的思路整理下，也还好，左下角代表的意思是判断中间部分是否回文。
双指针
class Solution {
public:
int extend(const string& s, int i, int j, int n){
int num=0;
while(i>=0&&j<n&&s[i]==s[j])
{
i--;
j++;
num++;
}
return num;
}
int countSubstrings(string s) {
int count = 0;
for(int i=0;i<s.size();i++)
{
count+=extend(s,i,i,s.size());
count+=extend(s,i,i+1,s.size());
}
return count;
}
};
双指针法确实好简单呢。只要一个个遍历中心点，然后朝两处扩散。注意，中心点可能是基数，也可能是偶数。所以要分两种情况，最开始我还担心，会不会数组越界。for循环怎么写。要在for循环后面补一行吗？但是子函数完全不用担心。因为虽然i+1==s.size(),能进入子函数，但是不能进入while循环，直接返回0。不用担心。
516. 最长回文子序列
- 回文子串，求的是回文子串，而本题要求的是回文子序列，大家要搞清楚两者之间的区别。
516. 最长回文子序列
最开始还以为回文子序列，直接双指针法秒了或者动态规划法秒了。结果发现回文子序列。确实难度增加了。得好好思考了。
class Solution {
public:
int longestPalindromeSubseq(string s) {
int count=0;
int n=s.size();
vector<vector<int>> dp(n , vector<int>(n , 0));
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
}
for (int i = n-2; i >=0; i--) {
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];
}
};
整体思路和原先完全类似，把这幅图的思路看懂即可。初始化要把对角线初始化为1，否则越界问题，以及不好初始化的问题。