假设你面前有一栋n层的大楼和m个鸡蛋，假设将鸡蛋从f层或更高的地方放扔下去，鸡蛋才会碎，否则就不会。你需要设计一种策略来确定f的值，求最坏情况下扔鸡蛋次数的最小值。
乍一看这道题很抽象，可能有的人一看到这个题目从来没做过，就懵逼了。其实不用慌张，再花里胡哨的题目，最后都可以抽象成我们熟悉的数据结构和算法去解决。
不限鸡蛋
首先，我们从一个简单的版本开始理解，假如不限制鸡蛋个数，即把题目改成n层大楼和无限个鸡蛋。那么这题要怎么解呢？
第一步就是要充分理解题意，排除题目中的干扰，建立模型：
- 在一栋n层的大楼中寻找目标楼层f --> 其实就是在一个1～n的数组中查找一个目标数字。
- 鸡蛋碎了就代表楼层过高，否则就代表楼层过低 --> 每次尝试都能知道当前数字是大了还是小了。
很显然，这就是一个二分查找能解决的问题。
扔鸡蛋的次数就是二分查找的比较次数，即$log_2(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 \leq j \leq n$，总时间复杂度为$O(mn^2)$。
优化
$O(mn^2)$的时间复杂度还是太高了。能不能想办法优化一下？
优化1
决策树
首先我们知道，在一个1～n的数组中，查找目标数字，最少需要比较$log_2n$次，也就是二分查找。这个理论可以通过决策树来证明：
我们使用二叉树来表示所有的决策，内部节点表示一次扔鸡蛋的决策，左子树表示碎了，右子树表示没碎，叶子节点代表E的所有结果。每一条从根节点到叶子节点的路径对应算法求出E之前的所有决策。
内部节点(i,j)，i表示鸡蛋个数，j表示在j层楼扔下。
当楼层高度n=5时，E总共有6种情况（n=0代表没找到），所以叶子节点的个数是n+1个。
而我们关心的是树的高度，即决策的次数。根据二叉树理论：当树有n个叶子节点，数的高度至少为$log_2n$，即比较次数在最坏情况下至少需要$log_2n$次，也就是当这颗树尽量平衡的时候。
换句话说，在给定楼层n的情况下，决策次数的下限是$log_2(n+1)$，这个下限可以通过二分查找达到，只要鸡蛋的数量足够（就是我们刚才讨论的不限鸡蛋的情况）。
因此，一旦状态f[i,j]的鸡蛋个数$i>log_2(j+1)$，就不用计算了，直接输出二分查找的比较次数$log_2(j+1)$即可。
这样我们的状态总数就降为$n*log_2(k+1)$，时间复杂度降为$O(n^2 log_2n)$。
代码
/**
* @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(log_2N)$，算法的时间复杂度降为$O(Nlog_2^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(\sqrt{N})$，证明比较复杂，这里就不展开了，可以参考文末文献。
小结
最后我们总结一下动态规划算法的解题方法：
- 四步走：问题建模、定义子问题、动态转移方程、最优子结构。
- 时间复杂度 = 状态总数 * 状态转移方程的时间复杂度。
- 考虑是否需要设置标记，例如有的题目还要求打印出最小路径。
- 写代码，递归和循环选择你熟悉的来写。
- 如果时间复杂度不能接受，考虑能不能优化算法。
优化思路
- 是否能够剪枝优化（优化1）
- 从函数本身的数学性质入手（优化2）
- 转换思路，尝试一下别的状态转移方程（优化3）
- ……
动态规划在算法中属于较难的题型，难点就在定义子问题和写出动态转移方程。所以需要勤加练习，训练自己的思维。
这里给出几道动态规划的经典题目，这几道题都需要吃透，可以用本文中提到的四步走的方式来思考和解题。
Maximum Length of Repeated Subarray
Coin Change
Partition Equal Subset Sum