LC 5. Longest Palindromic Substring

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> f(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++) f[i][i] = 1;
        int l = 0, r = 0;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s[i] == s[j]) {
                    if (i + 1 == j) f[i][j] = true;
                    else f[i][j] = f[i + 1][j - 1];
                }
                if (f[i][j] && ((r - l + 1) < (j - i + 1))) {
                    l = i;
                    r = j;
                }
            }
        }
        return s.substr(l, r - l + 1);
    }
};

恭喜你們看到下一種 DP 的套路題，這種類型的 DP 套路，我們稱之為區間型 DP。

這種類型的會有很明顯的從小區間開始解，往外解到大區間，他的轉移方程大致上會遵循以下。
dp[i][j] <- dp[i - 1][j] , dp[i][j - 1]

可以看到 dp[i][j] 是比較大的區間，而 dp[i - 1][j], dp[i][j - 1] 是比較小的區間，這就是所謂的區間型 DP。