1棍辕、題目
image.png
2暮现、分析
使用動(dòng)態(tài)規(guī)劃的方法。最重要的是明確dp數(shù)組的含義楚昭。
定義dp[i][j] 為字符串第i個(gè)位置栖袋，到第j個(gè)位置之間，最長(zhǎng)的回文序列長(zhǎng)度為dp[i][j]抚太。
由定義可以知道塘幅，i = j的時(shí)候，只有一個(gè)字符尿贫，最長(zhǎng)回文序列長(zhǎng)度為1电媳。
由于i >= j 所以，在i < j的地方都是0
我們因此可以得到base case：
image.png
具體分析過(guò)程可以看：
https://labuladong.github.io/zgnb/3/15/20/
3庆亡、代碼
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++){
if(i == j) dp[i][j] = 1;
else dp[i][j] = 0;
}
}
for(int i = n - 2; i >=0; i--){
for(int j = i + 1; j < n; j++){
if(s.charAt(i) == s.charAt(j))
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
}
}
return dp[0][n - 1];
}
}
