516. Longest Palindromic Subsequence

• 给定一个字符串s，找到以s为单位的最长回文子序列的长度。

• - LeetCode

思路

• 如果第一个和最后一个字符相同，那么长度+2

• 如果不同

• 那么这两个字符不会出现在同一个子串中

• 会出现两种情况

  • 删除左边的

  • 删除右边的

• 左右都有可能出现最长的，所以取这两种情况的最大值

• 之所以是子序列，是因为对于每个位置都进行了左右是否相同的判断，只要相同就会添加到候选中，所以能看到所有的结果。

代码

class Solution {
    private int lps(int i, int j, String s, int[][] memo){
        int longest = 0;
        if(memo[i][j] != 0){
            return memo[i][j];
        }
        if(i == j){
            //到中间那个
            return 1;
        }
        if(i > j){
            return 0;
        }

        if(s.charAt(i) == s.charAt(j)){
            // 如果两边一样，那么就长度就可以+2，因为内部不要求连续
            longest = lps(i+1, j-1, s, memo) + 2;
        }else{
            //两边不一样的时候，去一个左边的继续看，去一个右边的继续看，看是否能出现一样的。
            longest = Math.max(lps(i+1, j, s, memo), lps(i, j-1, s, memo));
        }
        memo[i][j] = longest;
        return longest;

    }
    public int longestPalindromeSubseq(String s) {
        return lps(0, s.length() - 1, s, new int[s.length()][s.length()]);
    }
}