# 516 - Longest Palindromic Subsequence

解法一 - 暴力法

這題的暴力解就是每一種 sequence 都檢查看看，所以一開始我們可以從字串的兩端開始處理，然後會有兩種情況：

1. 頭跟尾的字母相同：那我們就知道目前 sequence 的長度至少有 2，然後再繼續搜尋下去

2. 頭跟尾的字母不同：那就分別把頭往後移 & 尾往前移，得到兩個新的字串，然後分別搜尋

寫出來的程式碼如下：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        return findLPS(s, 0, s.length()-1);
    }

private:
    int findLPS(string& s, int start, int end) {
        if(start > end)
            return 0;

        // Any character is a palindrome with length 1
        if(start == end)
            return 1;

        if(s[start] == s[end])
            return 2+findLPS(s, start+1, end-1);

        int l1 = findLPS(s, start+1, end);
        int l2 = findLPS(s, start, end-1);
        return max(l1, l2);
    }
};

這個解法在 Leetcode 上面跑會 TLE。

解法二 - 暴力法 + Memoization

因為在變化的變數是 start & end，所以我們需要用一個 2D 的 memo table 來儲存

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> memo(s.length(), vector<int>(s.length(), -1));
        return findLPS(s, 0, s.length()-1, memo);
    }

private:
    int findLPS(string& s, int start, int end, vector<vector<int>>& memo) {
        if(start > end)
            return 0;

        // Any character is a palindrome with length 1
        if(start == end)
            return 1;

        if(memo[start][end] == -1) {
            if(s[start] == s[end]) {
                memo[start][end] = 2+findLPS(s, start+1, end-1, memo); 
            }
            else{
                int l1 = findLPS(s, start+1, end, memo);
                int l2 = findLPS(s, start, end-1, memo);
                memo[start][end] = max(l1, l2);        
            }
        }

        return memo[start][end];
    }
};

效率還不差： Runtime: 56 ms, faster than 86.91% of C++ online submissions for Longest Palindromic Subsequence. Memory Usage: 69.9 MB, less than 10.00% of C++ online submissions for Longest Palindromic Subsequence.

解法三 - DP

DP 解法的形式其實在上面就已經可以看出來，我們再來看一下詳細說明：

概念上頗為簡單，比較難一點的地方在於初始化，跟之前的比較不同：

另外就是構建 DP table 的順序也有點特別，因為我們最後的答案是在右上角，所以我們會從 start 最大的地方開始構建，然後 end 就從 start+1 開始到最後（如果 end < start，那就不用算）：

寫出來的程式碼如下：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.length(), vector<int>(s.length(), 0));

        // Init
        for(int i=0; i<s.length(); i++)
            dp[i][i] = 1;

        // Build DP table
        for(int start = s.length()-1; start>=0; start--) {
            for(int end = start+1; end<s.length(); end++) {
                if(s[start] == s[end])
                    dp[start][end] = 2 + dp[start+1][end-1];
                else
                    dp[start][end] = max(dp[start+1][end], dp[start][end-1]);
            }
        }

        return dp[0][s.length()-1];
    }
};