###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 516. Longest Palindromic Subsequence

## [題目連結:] https://leetcode.com/problems/longest-palindromic-subsequence/

## 題目:
Given a string ```s```, find the longest palindromic **subsequence**'s length in s.

A **subsequence** is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

**Example 1:**

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

**Example 2:**

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

## 解題想法:
* 此題為給一字符串，求最長的回文子序列長度
* 子序列: 不需要連續

* 使用DP:
* 定義dp[i][j]: **s[i]~s[j]中最長的回文長度**
* 初始: for i in range(len(s)): dp[i][i]=1
* dp[i][j]=case1+case2
* **case1:**
* 若當前首尾s[i]==s[j]相同，則繼承內縮的dp[i+1][j-1]，並再將長度+2
* dp[i][j]=dp[i+1][j-1]+2
* **case2:**
* 若首尾s[i]!=s[j]，則選則去掉 **s[i]** or **s[j]** 後對於dp結果最長者
* dp[i][j]=max(dp[i+1][j], dp[i][j-1

* 注意:
* 第一圈遍歷i從**尾到頭**!!
* 第二圈j為range(i+1~n)
* 因為最後是要求i=0，且確保j皆在i後面，若j>i，則dp[i][j]=0

## Python:

class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        #dp[i][j]: s[i]~s[j]可組成的最長回文
        #case1: if s[i]==s[j] 加2內縮: dp[i][j]= dp[i+1][j-1]+2 
        #case2: if s[i]!=s[j] : dp[i][j]=max(dp[i+1][j],dp[i][j-1]) 刪j or i
        n=len(s)
        dp=[[0 for _ in range(n)] for _ in range(n)]
        for i in range(n-1, -1, -1):
            dp[i][i]=1
            for j in range(i+1, n):
                if s[i]==s[j]:
                    dp[i][j]=dp[i+1][j-1]+2
                else:
                    dp[i][j]=max(dp[i+1][j], dp[i][j-1])
        return dp[0][n-1]               

## C++:

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        vector<vector<int>> dp(n, vector<int>(n,0));
        for (int i=n-1; i>=0; i--){
            dp[i][i]=1;
            for (int j=i+1; j<n; j++){
                if (s[i]==s[j])
                    dp[i][j]=dp[i+1][j-1]+2;
                else
                    dp[i][j]=max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][n-1];
    }
};