leetcode 516. Longest Palindromic Subsequence | 516. 最长回文子序列（递归 -＞傻缓存 -＞DP）

客官°小女子只卖身不卖艺 2022-09-12 01:48 60阅读 0赞

## 题目 ##

[https://leetcode.com/problems/longest-palindromic-subsequence/][https_leetcode.com_problems_longest-palindromic-subsequence]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

### 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];
        }
    }

[https_leetcode.com_problems_longest-palindromic-subsequence]: https://leetcode.com/problems/longest-palindromic-subsequence/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d1d211bd558b4b6395a3bfcc75c2a8d4.png