区间DP

87. 扰乱字符串

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n = s1.size();
        if (s1 == s2) return true;
        if (s1.size() != s2.size()) return false;
        vector<vector<vector<int>>>  f(n, vector<vector<int>>(n, vector<int>(n + 1, false)));

        // 处理长度为1的情况
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < n; j ++)
            if (s1[i] == s2[j]) f[i][j][1] = true;

        // f[i][j][len] 代表 s1s1 从 ii 开始，s2s2 从 jj 开始，后面长度为 lenlen 的字符是否能形成「扰乱字符串」（互为翻转）。
        for (int len = 2; len <= n; len ++) 
            for (int i = 0; i <= n - len; i ++) 
                for (int j = 0; j <= n - len; j ++)
                    for (int k = 1; k < len; k ++) { // 分割点
                        // a : 0 - i, b : 0 - j ; a: i - n, j - n
                        bool a = f[i][j][k] && f[i + k][j + k][len - k];
                        // a : 0 - i, b : n - i, n ; a: i - n, 0 - j
                        bool b = f[i][j + len - k][k] && f[i + k][j][len - k];
                        if (a || b) {
                            f[i][j][len] = true;
                        }
                    }
        return f[0][0][n];
    }
};

375. 猜数字大小 II

class Solution {
public:
    int getMoneyAmount(int n) {
        //定义 f[l][r]f[l][r] 为考虑在 [l, r][l,r] 范围内进行猜数的最小成本。
        vector<vector<int>> f(n + 2, vector<int>(n + 2, 0));
        
        // 需要找到能猜中数字的最小成本，也就是最坏情况最好的结果
        // 对于任一区间取min是因为我们在该区间可以先选择小的数去试，由此降低成本
        for (int len = 2; len <= n; len ++)
            for (int l = 1; l + len - 1 <= n; l ++) {
                int r = l + len - 1;
                f[l][r] = 0x3f3f3f3f;
                for (int x = l; x <= r; x ++) {
                    int cur = max(f[l][x - 1], f[x + 1][r]) + x;
                    f[l][r] = min(f[l][r], cur);
                }
            }
        return f[1][n];
    }
};

516. 最长回文子序列

class Solution {
public:
    /*
        bb aa bb
        bb a  bb
        dp[i][j] 表示 第 i 个字符到 第 j 个字符之间最长的回文子序列长度
        1、当 s[i] == s[j] 时，考虑 i 和 j 中间序列的奇偶个数， dp[i][j] = dp[i+1][j-1] + 2
        对上述 dp[i][j] =  dp[i+1][j-1] + 2 的解释：
        当序列为 b aa b 时， i = 0, j = 3，则 dp[0][3] = dp[1][2] + 2 = 4
        当序列为 b a b 时，i = 0, j = 2，则 dp[0][2] = dp[1][1] + 2 = 3 
        当序列为 b b 时， i = 0, j = 1，则 dp[0][1] = dp[1][0] = 0 + 2 = 2 (dp[1][0] 默认值为 0)
        该式子同时考虑到了奇偶
        2、当 s[i] != s[j] ，那么 dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1])
        对上述 dp[i][j] 式子的解释：
        假如序列为 d c b c c（index：0-4），s[0] != s[4] ，则 dp[0][4] = Math.max(dp[0][3],dp[1,4]) = Math.max(2,3) = 3
    */
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));

        for (int i = n - 1; i >= 0; i --) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j ++) {
                if (s[i] == s[j]) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                } else {
                    f[i][j] = max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        return f[0][n - 1];
    }
};

664. 奇怪的打印机

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.size();
        // f[i][j] 表示 区间[i,j]的最小打印次数
        vector<vector<int>> f(n + 1, vector<int>(n + 1, INT_MAX));
        for (int i = n - 1; i >= 0; i --) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j ++) {
                if (s[i] == s[j]) {
                    f[i][j] = f[i][j - 1];
                } else {
                    for (int k = i; k < j; k ++) {
                        f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
                    }
                }
            }
        }
        return f[0][n - 1];
    }
};

877. 石子游戏

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        // 定义 f[l][r]f[l][r] 为考虑区间 [l,r][l,r]，在双方都做最好选择的情况下，先手与后手的最大得分差值为多少
        vector<vector<int>> f(n + 2, vector<int>(n + 2, 0));

        for (int len = 1; len <= n;  len ++)
            for (int l = 1; l + len - 1 <= n; l ++) {
                int r = l + len - 1;
                int a = piles[l - 1] + f[l + 1][r];
                int b = piles[r - 1] + f[l][r - 1];
                f[l][r] = max(a, b);
            }
        return f[1][n] > 0;
    }
};