区间DP专题总结

区间DP是指以区间左右边界 f[i][j] 作为动态规划变量的问题

一般求解步骤：

1.状态定义：f[i][j] 为求解分区间 [i,j] 重复子问题的开销，其中 i<=j

2.状态转移：求f[i][j]通常要考虑将 [i, j] 区间分为两个重复子问题

这个根据具体的问题而定，有的可能要根据s[i]与s[j]是否相等做出不同的转移，如 664. 奇怪的打印机

有的可能是选择直接枚举分割点k，然后建立 [i, j] 区间与左右子区间的转移，如 375. 猜数字大小 II

有的还可能不是分割区间，而是利用缩小区间 [i+1,j] 的子问题与 [i, j] 区间建立连接，如 877. 石子游戏

3.初始化：通常来说要初始化长度为1的边界状态 f[i][i] 的值，为接下来的遍历做好初值准备

4.遍历顺序：这里有两种遍历的方法，推荐以遍历长度len的方法

4.1 长度len为基础进行遍历

1.遍历长度len(正序2~n)；

2.遍历左边界i(正序0~i+len-1==n-1)；

3.遍历分割点k(正反序无所谓i~j-1)

4.2 i与j为基础进行遍历

1.枚举左端点i(倒序n-2~0)

2.枚举右端点j(正序i+1~n-1)

3.枚举分割点k(正反序无所谓i~j-1)

此时以k分割后的左右子区间分别为：[i,k] 与 [k+1,j]

示意图如下：可知分割区间依赖于正下方和正左方的状态有效值->遍历长度是以“滑梯”的方式下去的；遍历i与j是从底下上来的

5.返回形式：一般来说返回 f[0][n-1] 就是关于整个区间对应的子问题答案

复杂度分析：一般地，时间复杂度:O(N^3)；空间复杂度:O(N^2)

375. 猜数字大小 II

class Solution {
    static int[][] f = new int[205][205];
    static final int INF = 0x3f3f3f3f;

    public int getMoneyAmount(int n) {
        /*
        解法2：区间DP
        1.状态定义:f[i][j]为确保猜中区间[i,j]至少需要的金额，其中 j>=i && i,j∈[1,n]
        2.状态转移:要想求解f[i][j]就要考虑f[i][k-1]与f[k+1][j]
            其中k为区间的分割点（某次猜的数字为k），遍历k∈[i,j]，求得该次稳赢的开销为 k+max(f[i][k-1],f[k+1][j])
            遍历k过程中维护[i,j]区间分割成两个区间后的最小值min，那么min就是f[i][j]的值
        3.初始化:f[i][j]=0 其中i>=j
        4.遍历顺序:求f[i][j]要用到f[i][k-1]与f[k+1][j] 那么j正序 i倒序 k无所谓
        5.返回形式:返回f[1][n]就是答案
         */
        // 遍历左边界i∈[n,1]
        for (int i = n; i >= 1; i--) {
            // 遍历右边界j∈[i+1,n] 注意j=i为0 强行转移会发生错误
            for (int j = i + 1; j <= n; j++) {
                int min = INF;
                // 遍历分界线k∈[i,j]
                for (int k = i; k <= j; k++) {
                    int cur = k + Math.max(f[i][k - 1], f[k + 1][j]);   // 本次猜k的稳赢的开销
                    min = Math.min(min, cur);   // 这么多种选择的最小开销
                }
                f[i][j] = min;
            }
        }
        return f[1][n];     // 选择[1,n]中稳赢的最小开销
    }
}

664. 奇怪的打印机

class Solution {
    public int strangePrinter(String s) {
        /*
        方法2：区间DP
        1.状态定义:f[i][j]为打印s[i,j]所需要的最少打印次数（i<=j）
        2.状态转移:求f[i][j]就要考虑s[i]与s[j]
            2.1 当s[i]==s[j]时 s[i]与s[j]其中一个可以顺路打印 f[i][j]=f[i][j-1]
            2.1 当s[i]=!s[j]时 枚举分割点，分割点两边的次数加起来取最小值就是答案(只取最优的打印次数转移)
                f[i][j]=min(f[i][k]+f[k+1][j]) 其中k∈[i,j-1]
        3.初始化:初始化f[i][i]=1 单个字符最少打印1次
        4.遍历顺序:Loop1->遍历长度len(正序)  Loop2->遍历左边界i(正序)  Loop3->遍历分割点k(正序)
            另一个遍历角度:枚举左端点i(倒序n-2~0) 枚举右端点j(正序i~n-1) 枚举分割点k(没所谓i~j-1)
        5.返回形式:返回f[0][n-1]就是打印s[0,n-1]所需要的最小打印次数
        时间复杂度:O(N^3) 空间复杂度:O(N^2)
         */
        int n = s.length(), INF = 101;
        int[][] f = new int[n][n];
        // 打印1个字符只需要1次
        for (int i = 0; i < n; i++) {
            f[i][i] = 1;
        }
        // 枚举长度len∈[2,len]
        for (int len = 2; len <= n; len++) {
            // 枚举左端点i∈[0,n-len]
            for (int i = 0; i + len - 1 < n; i++) {
                // j为右端点
                int j = i + len - 1;
                // s[i]==s[j] 顺路打印
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i][j - 1];
                } else {
                    int min = INF;  // 最多的打印次数
                    // 枚举分割点k∈[i,j-1]
                    for (int k = i; k < j; k++) {
                        // 维护最小的打印次数
                        min = Math.min(min, f[i][k] + f[k + 1][j]);
                    }
                    f[i][j] = min;
                }
            }
        }
        return f[0][n - 1];
    }
}

记忆化DFS解法：

class Solution {
    static int[][] memo;
    static final int INF = 101;
    char[] chs;

    public int strangePrinter(String s) {
        /*
        方法1：记忆化DFS:
        关注子问题，每当打印一段涉及到的变量为的当前打印区间的左右边界s[i,j]
        因此定义dfs(i,j)为打印s[i,j]需要的最少打印次数
        此时情况分为2种：
        1.当s[i]==s[j]时，打印s[i]时可以同时把s[j]也打印了，因此总的次数为dfs(i,j-1)
        2.当s[i]!=s[j]时，打印s[i]时不能同时把s[j]也打印
            假设中间的字母都不相同的情况下，总的次数需要dfs(i,j-1)+1，即每个字母都要独立打印
            但是s[i...k...j]中间的s[k]可能与s[i]或者s[j]相等，此时的打印次数可以减少，因为可以顺带打印
            那么就要枚举s[i,j]之间的分割点s[k]，其中k∈[i,j-1]，分割后的区间为s[i,k]与s[k+1,j]
            最少的打印次数为多少？答案为min(dfs(i,k)+dfs(k+1,j)) 中间可以顺带打印的都经过了最优的状态转移
        最后返回dfs(0,n-1)就是答案
         */
        chs = s.toCharArray();
        int n = chs.length;
        memo = new int[n][n];
        return dfs(0, n - 1);
    }

    // dfs(i,j):打印s[i,j]需要的最少打印次数
    private int dfs(int i, int j) {
        // memo中存在该状态直接返回
        if (memo[i][j] != 0) return memo[i][j];
        // base case
        if (i == j) return 1;
        // s[i]==s[j]
        if (chs[i] == chs[j]) return dfs(i, j - 1);
        int min = INF;
        for (int k = i; k < j; k++) {
            min = Math.min(min, dfs(i, k) + dfs(k + 1, j)); // 取最小分割位置赋值到dfs(i,j)
        }
        memo[i][j] = min;
        return min;
    }
}