赞
踩
题目链接:https://leetcode.cn/problems/palindromic-substrings/
dp数组的含义
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]代表是[i,j-1]中含有多少个回文子串
递推公式
本题有两种情况:
s
[
i
,
j
−
1
]
s[i,j-1]
s[i,j−1]是回文子串
显然此时递推公式为:
d
p
[
i
]
[
j
]
=
d
p
[
i
]
[
j
−
1
]
+
1
dp[i][j] = dp[i][j-1]+1
dp[i][j]=dp[i][j−1]+1
s
[
i
,
j
−
1
]
s[i,j-1]
s[i,j−1]不是回文子串
此时递推公式为:
d
p
[
i
]
[
j
]
=
d
p
[
i
]
[
j
−
1
]
dp[i][j] = dp[i][j-1]
dp[i][j]=dp[i][j−1]
初始化
都初始化为0即可,因为在后面会被覆盖掉。
遍历顺序
显然遍历是从上到下,从左到右
class Solution { public: int countSubstrings(string s) { vector<vector<int>>dp(s.size() + 1, vector<int>(s.size() + 1, 0)); // for(int i = 1; i <= s.size(); i++) // dp[i][i] = 1; for(int i = 0; i <= s.size(); i++) { for(int j = i + 1; j <= s.size(); j++) { if(isPalindromic(s, i, j - 1)) dp[i][j] = dp[i][j - 1] + 1; else dp[i][j] = dp[i][j - 1]; } } int result = 0; for(int i = 0; i <= s.size(); i++) { result += dp[i][s.size()]; // cout << dp[i][s.size()]; } return result; } bool isPalindromic(string s, int start, int end) { for(int i = start, j = end; i <= j; i++, j--) { if(s[i] != s[j]) return false; } return true; } };
dp数组的含义
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]代表[i,j]是否是回文子串
递推公式
本题有两种情况:
s[i] == s[j]
这个时候又有三种情况:
1. i=j,例子:a;此时必然是回文子串
2. j - i = 1,即:aa;此时同然是回文子串
这两种情况递推公式都是
d
p
[
i
]
[
j
]
=
t
r
u
e
dp[i][j] =true
dp[i][j]=true
3. j- i > 1,即abcsda,这个时候就要判断[i+1,j-1]是否是回文子串了,如果是的话,那么[i,j]也是回文子串
所以整体的递推公式为:
if (s[i] == s[j])
{
if (j - i <= 1)
{ // 情况一 和 情况二
result++;
dp[i][j] = true;
}
else if (dp[i + 1][j - 1])
{ // 情况三
result++;
dp[i][j] = true;
}
}
初始化
因为如果不是回文子串的话,赋值为false即可,而且为了不被初始化影响,所以值都初始化为false
遍历顺序
由递推公式可知:
如果这矩阵是从上到下,从左到右遍历,那么会用到没有计算过的
d
p
[
i
+
1
]
[
j
−
1
]
dp[i + 1][j - 1]
dp[i+1][j−1],也就是根据不确定是不是回文的区间[i+1,j-1],来判断了[i,j]是不是回文,那结果一定是不对的。
所以一定要从下到上,从左到右遍历,这样保证 d p [ i + 1 ] [ j − 1 ] dp[i + 1][j - 1] dp[i+1][j−1]都是经过计算的。
class Solution { public: int countSubstrings(string s) { int result = 0; vector<vector<bool>>dp(s.size(), vector<bool>(s.size(), false)); 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) { dp[i][j] = true; result++; } else { if(dp[i + 1][j - 1]) { dp[i][j] = true; result++; } } } } } return result; } };
想到了第一种方法,但是时间和内存花费都比较大。
题目链接:https://leetcode.cn/problems/longest-palindromic-subsequence/
dp数组的含义
dp[i][j]dp[i][j] 表示在[i,j]内最长的回文子序列长度
递推公式
本题要求的是子序列,和子串最大的不同就是,本题不需要连续。
本题主要还是看s[i]和s[j]是否相同
s
[
i
]
=
s
[
j
]
s[i]=s[j]
s[i]=s[j]
此时递推公式为:
d
p
[
i
]
[
j
]
=
d
p
[
i
+
1
]
[
j
−
1
]
+
2
dp[i][j]=dp[i+1][j-1]+2
dp[i][j]=dp[i+1][j−1]+2
(没想明白的话要看一看dp数组的含义)
当
s
[
i
]
!
=
s
[
j
]
s[i]!=s[j]
s[i]!=s[j]
此时要考虑,包含i,即[i,j-1]内最长的回文子序列长度和包含j,即[i+1,j]内最长的回文子序列长度中哪个更长
所以递推公式为:
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
]
[
j
−
1
]
,
d
p
[
i
+
1
]
[
j
]
dp[i][j]=max(dp[i][j-1],dp[i+1][j]
dp[i][j]=max(dp[i][j−1],dp[i+1][j]
初始化
首先要考虑当i 和j 相同的情况,从递推公式:
d
p
[
i
]
[
j
]
=
d
p
[
i
+
1
]
[
j
−
1
]
+
2
dp[i][j] = dp[i + 1][j - 1] + 2
dp[i][j]=dp[i+1][j−1]+2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。
所以需要手动初始化一下,当i与j相同,那么
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]一定是等于1的,即:一个字符的回文子序列长度就是1。
其他情况dp[i][j]初始为0就行,这样递推公式:
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
+
1
]
[
j
]
,
d
p
[
i
]
[
j
−
1
]
)
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
dp[i][j]=max(dp[i+1][j],dp[i][j−1])中
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]才不会被初始值覆盖。
遍历顺序
由图片可知,
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]依赖于
d
p
[
i
+
1
]
[
j
−
1
]
dp[i + 1][j - 1]
dp[i+1][j−1],
d
p
[
i
+
1
]
[
j
]
dp[i + 1][j]
dp[i+1][j]和
d
p
[
i
]
[
j
−
1
]
dp[i][j - 1]
dp[i][j−1],所以要从下往上,再从左到右。
class Solution { public: int longestPalindromeSubseq(string s) { vector<vector<int>>dp(s.size(), vector<int>(s.size(), 0)); for(int i = 0; i < s.size(); i++) dp[i][i] = 1; for(int i = s.size() - 1; i >= 0; i--) { for(int j = i + 1; j < s.size(); 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][s.size() - 1]; } };
子序列和子串的最大不同就在于子序列可以不连续
动态规划结束了!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。