5. Longest Palindromic Substring

 動規五部曲分別為:

1. 確定dp數組(dp table)以及下標的含義

2. 確定遞推公式

3. dp數組如何初始化

4. 確定遍歷順序

5. 舉例推導dp數組

(from 代碼隨想錄)

1. 確定dp數組(dp table)以及下標的含義

dp[i][j] 表示 s[i..j] 是否為回文字串

2. 確定遞推公式

如果 s[i] == s[j] 而且  s[i+1..j-1] 是回文字串的話(如果長度<=2就不用檢查這個條件)，那 s[i..j] 也是回文字串

if(s[i] == s[j] && (j-i <= 2 || dp[i+1][j-1]))

     dp[i][j] = true;

3. dp數組如何初始化

default false

4. 確定遍歷順序

要根據狀態來決定初始化，又因為dp[i][j]會看dp[i+1][j-1]，所以應該是i由大到小、j由小到大

5. 舉例推導dp數組

略

class Solution {

public:

    string longestPalindrome(string s) {

        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));

        for(int i=0; i<s.size(); i++)

            dp[i][i] = true; // init

        string ans = "";

        for(int i=s.size()-1; i>=0; i--)

        {

            for(int j=i; j<s.size(); j++)

            {

                if(s[i] == s[j] && (j-i <= 2 || dp[i+1][j-1]))

                {

                    dp[i][j] = true;

                    ans = j-i+1 > ans.size() ? s.substr(i, j-i+1) : ans;

                }

            }

        }

        return ans;

    }

};

不過這題其實用DP很慢，純粹是練習DP而已XD