这个面试还出得挺多的,简单梳理一下思路
设计
- 识别问题:区间问题、能用重叠子问题来推 -> 区间DP
- 状态表示:区间 i, j 属性为最长的回文字串数
dp[i][j]
状态计算,分两种情况- 01 s[i] = s[j],等于都往里靠一个位置,再
+2
- 02 s[i] != s[j],这个不太好想,大概逻辑是新考虑的两个字符直接加肯定是加不成了,但是要考虑完整所有的子情况,那就是考虑两个位置各不考虑的情况的最大值,也就是
i, j-1
和i+1, j
然后是遍历顺序的确定,大致就是一个从中间往两边的顺序。画个格子更好理解,遍历的时候使用截距来遍历就行了。
还有另一种顺序,就是 i 递减,j 递增。
实现
int longestPalindromeSubseq(string s) {
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int c = 0; c < n; c++) {
for (int j = c; j < n; j++) {
int i = j - c;
if (i == j) dp[i][j] = 1;
else 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];
}