题目

https://leetcode.com/problems/longest-palindromic-subsequence/

题解

1、递归（超时）

递归 -> 傻缓存 ->DP

class Solution {
    public int longestPalindromeSubseq(String s) {
        if (s.length() == 0) return 0;
        return process(s, 0, s.length() - 1);
    }

    public int process(String s, int L, int R) {
        if (L < 0 || R == s.length() || L > R) return 0;

        if (L == R) {
            return 1;
        }

        int p1 = process(s, L + 1, R - 1);
        int p2 = process(s, L, R - 1);
        int p3 = process(s, L + 1, R);
        int p4 = s.charAt(L) == s.charAt(R) ? process(s, L + 1, R - 1) + 2 : 0;

        int res = Math.max(Math.max(p1, p2), Math.max(p3, p4));
        return res;
    }
}

2、傻缓存（AC）

class Solution {
    public int longestPalindromeSubseq(String s) {
        if (s.length() == 0) return 0;
        int[][] dp = new int[s.length()][s.length()];
        return process(s, 0, s.length() - 1, dp);
    }

    public int process(String s, int L, int R, int[][] dp) {
        if (L < 0 || R == s.length() || L > R) return 0;
        if (dp[L][R] != 0) return dp[L][R];

        if (L == R) {
            dp[L][R] = 1;
            return 1;
        }

        int p1 = process(s, L + 1, R - 1, dp);
        int p2 = process(s, L, R - 1, dp);
        int p3 = process(s, L + 1, R, dp);
        int p4 = s.charAt(L) == s.charAt(R) ? process(s, L + 1, R - 1, dp) + 2 : 0;
        
        int res = Math.max(Math.max(p1, p2), Math.max(p3, p4));
        dp[L][R] = res;
        return res;
    }
}

3、dp（AC）

class Solution {
    public int longestPalindromeSubseq(String s) {
        if (s.length() == 0) return 0;
        int N = s.length();
        int[][] dp = new int[N][N];
        // base case
        for (int i = 0; i < N; i++) {
            dp[i][i] = 1;
        }
        // 根据递归填写依赖
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N - i - 1; j++) {
                int L = j;
                int R = i + j + 1;
                int p1 = dp[L + 1][R - 1];
                int p2 = dp[L][R - 1];
                int p3 = dp[L + 1][R];
                int p4 = s.charAt(L) == s.charAt(R) ? dp[L + 1][R - 1] + 2 : 0;
                dp[L][R] = Math.max(Math.max(p1, p2), Math.max(p3, p4));
            }
        }
        return dp[0][N - 1];
    }
}