假设你面前有一栋n层的大楼和m个鸡蛋,假设将鸡蛋从f层或更高的地方放扔下去,鸡蛋才会碎,否则就不会。你需要设计一种策略来确定f的值,求最坏情况下扔鸡蛋次数的最小值。
乍一看这道题很抽象,可能有的人一看到这个题目从来没做过,就懵逼了。其实不用慌张,再花里胡哨的题目,最后都可以抽象成我们熟悉的数据结构和算法去解决。
不限鸡蛋
首先,我们从一个简单的版本开始理解,假如不限制鸡蛋个数,即把题目改成n层大楼和无限个鸡蛋。那么这题要怎么解呢?
第一步就是要充分理解题意,排除题目中的干扰,建立模型:
- 在一栋n层的大楼中寻找目标楼层f --> 其实就是在一个1~n的数组中查找一个目标数字。
- 鸡蛋碎了就代表楼层过高,否则就代表楼层过低 --> 每次尝试都能知道当前数字是大了还是小了。
很显然,这就是一个二分查找能解决的问题。
扔鸡蛋的次数就是二分查找的比较次数,即log2(n+1)。
限制鸡蛋个数
那我们现在再来看限制鸡蛋个数情况下,肯定没法用二分查找,但是由于求解的是一个最优值,我们自然而然地想到了动态规划。
四步走
动态规划的题目,这边提供一个思路,就是四步走:
- 问题建模,优化的目标函数是什么?约束条件是什么?
- 划分子问题(状态)
- 列出状态转移方程及初值
- 是否满足最优子结构性质
建模
这一步非常非常重要,它建立在良好地理解题意的基础上。其实很多动态规划的题目都有这样的特点:
- 目标是求一个最优值
- 每一步决策有代价,总代价有一个约束值。
而这道题:
- 目标函数
f(n)
:代表在1~n的楼层中找到f层的尝试次数,我们的目标就是求出f(n)
的最优值。 - 每一步决策的代价:鸡蛋可能会碎;总代价的约束值:鸡蛋总个数。
划分子问题
我们知道动态规划就是多阶段决策的过程,最后求解组合最优值。
我们先举一个简单例子,来理解划分子问题的思路,看下面这张图:
问题:求起点集 S1~S5到终点集 T1~T5的最短路径。
分析这道题:定义子问题dis[i]
代表节点i到终点的最短距离,没有约束条件。
然后问题划分为4个阶段:
- 阶段1求出离终点最近的
C1~C4
节点到终点的最短路径dis[C1]~dis[C4]
。 - 阶段2求出离终点最近的
B2~B5
节点到终点的最短路径dis[B1]~dis[B5]
,需要建立在阶段1的结果上计算。例如B2节点到终点有两条路,B2~C1,B2~C2,dis[C1]=2,B2到C1的长度=3;而dis[C2]=3,B2到C2的长度=6,因此dis[B2]=3+dis[B1]=5
。 - 阶段3和阶段4也是以此类推,最终就求出得到
dis[S1]~dis[S5]
,得出最小路径为图中红色的两条。
在这道题中,dis[i]
就是划分出来的子问题,每一步决策都是一个子问题,而且每一个子问题都依赖于以前子问题的计算结果。
因此,在动态规划中,定义一个合理的子问题非常重要。
而扔鸡蛋这道题比上面这道题多了个约束条件,我们把子问题定义为:用i个鸡蛋,在j层楼上扔,在最坏情况下确定目标楼层E的最少次数,记为状态f[i,j]
。
列出状态转移方程和初值
假如决策是在第k层扔下鸡蛋,有两种结果:
- 鸡蛋碎了,此时
e<k
,我们只能用i-1个蛋在下面的j-1层继续寻找e。并且要求最坏情况下的次数最少,这是一个子问题,答案为f[i-1,j-1]
,总次数便是f[i-1,j-1]+1
。 - 鸡蛋没碎,此时
e>=k
,我们继续用这i个蛋在上面的j-k层寻找E。注意:在k~j层寻找和在1~(j-k)层寻找没有区别,因为步骤都是一样的,只不过这(j-k)层在上面罢了,所以就把它看成是对1~(j-k)层的操作。因此答案为f[i,j-k]
,次数为f[i,j-k]+1
。
初值:
当层数为0时,f[i,0]=0
,当鸡蛋个数为1时,只能从下往上一层层扔,f[1,j]=j
。
因为是要最坏情况,所以这两种情况要取大值:max{f[i-1,j-1],f[i,j-k]}
,又要在所有决策中取最小值,所以动态转移方程是:
f(i,j)=min{max{f(i-1,k-1),f(i,j-k)}+1|1<=k<=j}
是否满足最优子结构
得到了状态转移方程后,还需要判断我们的思路是不是正确。能用动态规划解决的问题必须要满足一个特性,叫做最优子结构特性。
这句话是什么意思呢?举个例子:f[4,5]
表示4个鸡蛋、5层楼时的最优解
,那它的子问题f[3,4]
,得到的解在3个鸡蛋、4层楼时
也是最优解,它所有的子问题都满足这个特性。那这就满足了最优子结构特性。
一个反例
求 路径长度模10 结果最小的路径
还是像上面那道题一样,分成四个阶段。
按照动态规划的解法,阶段一CT
,上面的路2 % 10 = 2
,下面的路5 % 10 = 5
,选择上面那条,阶段二BC
也选择上面那条,以此类推,最后得出的结果路径是蓝色的这条。
但实际上,真正最优的是红色的这条路径20 % 10 = 0
。这就是因为不符合最优子结构,对于红色路径的子结构CT
阶段,最优解并不是下面这条边。
时间复杂度
递归树
假设m=3,n=4,我们来看一下f[3,4]的递归树。
图中颜色相同的就是一样的状态,可以看出,重复的递归计算很多,因此我们开设一个数组result[i,j]
用于存放f[i,j]
的计算结构,避免重复计算,用空间换时间。
代码
class Solution {
private int[][] result;
public int superEggDrop(int K, int N) {
result = new int[K + 1][N + 1];
for (int i = 1; i < K + 1; i++) {
for (int j = 1; j < N + 1; j++) {
result[i][j] = -1;
}
}
return dp(K, N);
}
/**
* @param i 剩余鸡蛋个数
* @param j 楼层高度
* @return
*/
private int dp(int i, int j) {
if (result[i][j] != -1) {
return result[i][j];
}
if (i == 1) {
return j;
}
if (j <= 1) {
return j;
}
int min = Integer.MAX_VALUE;
for (int k = 1; k <= j; k++) {
int left = dp(i - 1, k - 1);
result[i - 1][k - 1] = left;
int right = dp(i, j - k);
result[i][j - k] = right;
int res = Math.max(left, right) + 1;
if (res < min) {
min = res;
}
}
return min;
}
private static int log(int x) {
double r = (Math.log(x) / Math.log(2));
if ((r == Math.floor(r)) && !Double.isInfinite(r)) {
return (int) r;
} else {
return (int) r + 1;
}
}
}
时间复杂度
动态规划求时间复杂度的方法是:
时间复杂度 = 状态总数 * 状态转移方程的时间复杂度
在这道题中,状态总个数很明显是m*n
,而每个状态f[i,j]
的时间复杂度为O(j),1<=j<=n,总时间复杂度为O(mn^2)。
优化
O(mn^2)的时间复杂度还是太高了。能不能想办法优化一下?
优化1
决策树
首先我们知道,在一个1~n的数组中,查找目标数字,最少需要比较log2n次,也就是二分查找。这个理论可以通过决策树来证明:
我们使用二叉树来表示所有的决策,内部节点表示一次扔鸡蛋的决策,左子树表示碎了,右子树表示没碎,叶子节点代表E的所有结果。每一条从根节点到叶子节点的路径对应算法求出E之前的所有决策。
内部节点(i,j),i表示鸡蛋个数,j表示在j层楼扔下。
当楼层高度n=5时,E总共有6种情况(n=0代表没找到),所以叶子节点的个数是n+1个。
而我们关心的是树的高度,即决策的次数。根据二叉树理论:当树有n个叶子节点,数的高度至少为log2n,即比较次数在最坏情况下至少需要log2n次,也就是当这颗树尽量平衡的时候。
换句话说,在给定楼层n的情况下,决策次数的下限是log2(n+1),这个下限可以通过二分查找达到,只要鸡蛋的数量足够(就是我们刚才讨论的不限鸡蛋的情况)。
因此,一旦状态f[i,j]的鸡蛋个数i>log2(j+1),就不用计算了,直接输出二分查找的比较次数log2(j+1)即可。
这样我们的状态总数就降为n*log2(k+1),时间复杂度降为O(n^2 log2n)。
代码
/**
* @param i 剩余鸡蛋个数
* @param j 楼层高度
* @return
*/
private int dp(int i, int j) {
if (result[i][j] != -1) {
return result[i][j];
}
if (i == 1) {
return j;
}
if (j <= 1) {
return j;
}
//此处剪枝优化
int lowest = log(j + 1);
if (i > lowest) {
return lowest;
}
int min = Integer.MAX_VALUE;
for (int k = 1; k <= j; k++) {
int left = dp(i - 1, k - 1);
result[i - 1][k - 1] = left;
int right = dp(i, j - k);
result[i][j - k] = right;
int res = Math.max(left, right) + 1;
if (res < min) {
min = res;
}
}
return min;
}
优化2
优化还未结束,我们尝试从动态转移方程的函数性质入手,观察函数f(i,j),如下图:
我们可以发现一个规律,f(i,j)是根据j递增的单调函数,即f(i,j)>=f(i,j-1)
,这个性质是可以用数学归纳法证明的,在这里不做证明,有兴趣的查看文末参考文献。
再来看动态转移方程:
f(i,j)=min{max{f(i-1,k-1),f(i,j-k)}+1|1<=k<=j}
由于f(i,j)具有单调性,因此f(i-1,k-1)是根据k递增的函数,f(i,j-k)是根据k递减的函数。
分别画出这两个函数的图像:
图像1:f(i-1,k-1)
图像2:f(i,j-k)
图像3:max{f(i-1,k-1),f(i,j-k)}+1,当k=kbest时,f达到最小值,我们的目标就是找到kbest的值。
对于这个函数,可以使用二分查找来找到kbest:
如果f(i-1,k-1)<f(i,j-k)
,则k<kbest,即k在图中kbest的左边;
如果f(i-1,k-1)>f(i,j-k)
,则k>kbest,即k在图中kbest的右边。
代码
class EggDrop {
private int[][] result;
public int superEggDrop(int K, int N) {
result = new int[K + 1][N + 1];
for (int i = 1; i < K + 1; i++) {
for (int j = 1; j < N + 1; j++) {
result[i][j] = -1;
}
}
return dp(K, N);
}
/**
* @param i 剩余鸡蛋个数
* @param j 楼层高度
* @return
*/
private int dp(int i, int j) {
if (result[i][j] != -1) {
return result[i][j];
}
if (i == 1) {
return j;
}
if (j <= 1) {
return j;
}
int lowest = log(j + 1);
if (i >= lowest) {
result[i][j] = lowest;
return lowest;
}
int left = 1, right = j;
while (left <= right) {
int k = (left + right) / 2;
int broken = dp(i - 1, k - 1);
result[i - 1][k - 1] = broken;
int notBroken = dp(i, j - k);
result[i][j - k] = notBroken;
if (broken < notBroken) {
left = k + 1;
} else if (broken > notBroken) {
right = k - 1;
} else {
return notBroken + 1;
}
}
//没找到,最小值就在left或者right中
return Math.min(Math.max(dp(i - 1, left - 1), dp(i, j - left)),
Math.max(dp(i - 1, right - 1), dp(i, j - right))) + 1;
}
private static int log(int x) {
double r = (Math.log(x) / Math.log(2));
if ((r == Math.floor(r)) && !Double.isInfinite(r)) {
return (int) r;
} else {
return (int) r + 1;
}
}
}
时间复杂度
现在状态转移方程的时间复杂度降为了O(log2N),算法的时间复杂度降为O(Nlog2^2 N)。
优化3
现在无论是状态总数还是状态转移方程都很难优化了,但还有一种算法有更低的时间复杂度。
我们定义一个新的状态g(i,j),它表示用j个蛋尝试i次在最坏情况下能确定E的最高楼层数。
动态转移方程
假设在k层扔下一只鸡蛋:
如果碎了,则在后面的(i-1)次里,我们要用(j-1)个蛋在下面的楼层中确定E。为了使 g(i,j)达到最大,我们当然希望下面的楼层数达到最多,这是一个子问题,答案为 g(i-1,j-1)。
如果没碎,则在后面(i-1)次里,我们要用j个蛋在上面的楼层中确定E,这同样需要楼层数达到最多,便为g(i-1,j) 。
因此动态转移方程为:
g(i,j)=g(i-1,j-1)+g(i-1,j)+1
边界值
当i=1时,表示只尝试一次,那最多只能确定一层楼,即g(1,j)=1 (j>=1)
当j=1是,表示只有一个蛋,那只能第一层一层层往上扔,最坏情况下一直扔到顶层,即g(i,1)=i (i>=1)
。
然后我们的目标就是找到一个尝试次数x,使x满足g(x-1,m)<n
且g(x,m)>=n
。
代码
public class EggDrop {
private int dp(int iTime, int j) {
if (iTime == 1) {
return 1;
}
if (j == 1) {
return iTime;
}
return dp(iTime - 1, j - 1) + dp(iTime - 1, j) + 1;
}
public int superEggDrop(int i, int j) {
int ans = 1;
while (dp(ans, i) < j) {
ans++;
}
return ans;
}
}
这个算法的时间复杂度是O(根号N),证明比较复杂,这里就不展开了,可以参考文末文献。
小结
最后我们总结一下动态规划算法的解题方法:
- 四步走:问题建模、定义子问题、动态转移方程、最优子结构。
- 时间复杂度 = 状态总数 * 状态转移方程的时间复杂度。
- 考虑是否需要设置标记,例如有的题目还要求打印出最小路径。
- 写代码,递归和循环选择你熟悉的来写。
- 如果时间复杂度不能接受,考虑能不能优化算法。
优化思路
- 是否能够剪枝优化(优化1)
- 从函数本身的数学性质入手(优化2)
- 转换思路,尝试一下别的状态转移方程(优化3)
- ……
动态规划在算法中属于较难的题型,难点就在定义子问题和写出动态转移方程。所以需要勤加练习,训练自己的思维。
这里给出几道动态规划的经典题目,这几道题都需要吃透,可以用本文中提到的四步走的方式来思考和解题。
Maximum Length of Repeated Subarray
Coin Change
Partition Equal Subset Sum