
相关模板:
int n = arr.length;
int[][] dp = new dp[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if (arr[i] == arr[j])
dp[i][j] = dp[i][j] + ...
else
dp[i][j] = 最值(... )
}
}
- 集合划分
- 两个目标时:在子数组 arr1[0...i] 和子数组 arr2[0...j] 中,我们要求的子序列的长度为 dp[i][j]
- 一个目标时:在子数组 arr[i....j] 中,我们要求子序列的长度为dp[i][j]
AC代码:
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));//动态转移数组全为0
for (int i = 0; i < n; i++) dp[i][i] = 1;//初始化,在s(i,j) 当 i == j 时,只有一个字符(回文串)
//确保 左、左下、下 的状态能先计算出来,选择向后开始状态转移,参考状态一
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] + 2;//参考状态二图片
else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);//参考状态三图片
}
return dp[0][n-1];
}
};
状态一:

状态二:

状态三:

本文链接:
https://nullcode.fun/167.html