# 0516. Longest Palindromic Subsequence
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/longest-palindromic-subsequence/
## 思路
典型第II类区间型DP题

## Code

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for(int len = 1; len<=n; len++){
            for(int i=0; i+len-1<n; i++){
                int j = i+len-1;
                if(i==j) dp[i][j]=1;
                else 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]);
            }
        }
        return dp[0][n-1];
    }
}