区间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是从底下上来的

p9

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;
}
}

其实能用动态规划解决的问题都可以用记忆化DFS解决

记忆化DFS的优点就是不用考虑具体的状态遍历顺序是怎样的,只要能够判断出memo里面的状态被有效值覆盖过就可以直接拿来用,因此可以将 memo[i][j] 的值初始化为一个不可能到达的值INF

模板中一般包含一下几个关键点:

1.每次递归返回之前记录该次最优值进入memo memo[i][j] = min;

2.若dfs(i,j)中的memo[i][j]的有效值已经出现过可以直接取 if (memo[i][j] != 0) return memo[i][j];

3.base case 一般来说是 if (i == j) return ?;

4.遍历与dfs(i,j)有关的状态(结果),选择最优的(经过计算)得到的结果作为dfs(i,j)的结果 视具体问题而定