0动态规划中等 NC154 最长回文子序列

描述

给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。字符串长度<=5000 回文序列是指这个序列无论从左读还是从右读都是一样的。

分析

dp[i][j]表示i到j之间最长回文子序列的长度。

当s.charAt(i)， s.charAt(j)相等时， dp[i][j] = dp[i+1][j-1] + 2;

当s.charAt(i)， s.charAt(j)不相等时，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。因此，dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);

初始条件dp[i][i]等于1.

遍历顺序：dp[i][j] 取决于它的下层和左侧，因此由下往上，由左往右遍历。

import java.util.*;
public class Solution {
    public int longestPalindromeSubSeq (String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        int res = 1;
        for(int i = n - 1; i >= 0; i--){
            dp[i][i] = 1;
            for(int j = i + 1; j < n; j++){//若j = i ;当i == 0时，dp[i][j-1]或者dp[i+1][j-1]会出界。
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
                res = Math.max(res,dp[i][j]);
            }
        }
        return res;
    }
}