动态规划主要解决的是重叠子问题，并减少计算次数。他和分治算法，贪心算法有什么区别呢？分治算法的每个子问题都是独立的且和原问题相同，他是把一个大的问题不断拆成小的子问题，然后将子问题的解合并得到原问题的解。贪心算法只依赖当前的状态做出选择，不依赖前面解决的子问题，他是自顶往下一步步做出选择。动态规划他的每一步选择不光和当前状态有关，有的还和之前子问题的状态有关，他会把计算的结果保存下来，因为有重复子问题，所以下次遇到重复的问题不会在重复计算。重叠子问题不是使用动态规划的必要条件，但又重叠子问题更能彰显动态规划的优势，动态规划的本质就是：动态规划 = 搜索 + 备忘录，也就是说如果数据量特别小或者不考虑重复计算的情况下，动态规划都是可以使用搜索来解决。
我们来看下动态规划最入门的一道题-爬楼梯，假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以爬 1 或 2个台阶，你有多少种不同的方法可以爬到楼顶？如果要爬到第 n 个台阶，有两种方式，一种是从 n-1 个台阶爬一步上来，还一种是从 n-2 个台阶爬两步上来，这是两种不同的选择，结果就是他俩的和。如果我们定义 f(n) 表示到达台阶 n 需要的方案数，我们可以得到下面公式。
f(n) = f(n-1) + f(n-2) 。
实际上他就是一个斐波那契数列。
代码如下：
public int f(int n) {
if (n <= 2)
return n;
return f(n - 1) + f(n - 2);
}
如果使用递归计算的时候，就会有大量的重复计算。怎么解决这个问题呢？就是使用备忘录，计算之后就把结果存储起来，下次用的时候如果有就直接拿来用，如果没有在计算。
public int f(int n, int[] map) {
if (n <= 2)
return n;
if (map[n] == 0)// 如果没计算就先计算，如果计算过就不在计算。
map[n] = f(n - 1, map) + f(n - 2, map);
return map[n];
}
来看下他的计算过程，如下图所示。可以把他想象成为二叉树的后序遍历，从下往上计算，其中灰色的是已经计算过的，不需要重复计算。
除了节点 1 和 2 以外，剩下节点计算过程可以把他看做是对一个数组从前往后计算，如果知道 dp[i-2] 和 dp[i-1] 的值，就可以计算 dp[i] 的值，这是一个递推的过程。
public int climbStairs(int n) {
if (n <= 1)
return 1;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2];// 递推
return dp[n];
}
这就是动态规划，如果想求当前问题的值，必须知道子问题的值，至于子问题是怎么计算的，我们不用管。在 quora 上有这样一个问题，他很好的回答了什么是动态规划。
How should I explain dynamic programming to a 4-year-old?
*writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper*
"What's that equal to?"
*counting* "Eight!"
*writes down another "1+" on the left*
"What about that?"
*quickly* "Nine!"
"How'd you know it was nine so fast?"
"You just added one more"
"So you didn't need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'"
大概意思是这样，如果在加一个数字，只需要知道之前的结果即可，不需要在全部计算一遍。
我该如何向一个4岁的孩子解释动态规划?
A 1+1+1+1+1+1+1+1 =?
B 等于 8
A 如果在等式的左边加上 1+ 呢？
B 等于 9
A 你怎么知道这么快。
B 只要在 8 的基础上加上 1 就行了。
A 所以你不需要重新计算，因为你知道之前等式的结果是 8 。动态规划就是通过计算之前的解来节省时间。
兑换零钱(一)
给定数组 coins ， coins 中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个 amount ，代表要找的钱数，求组成 amount 的最少货币数。如果无解，请返回 -1 。
Input：[5,2,3],20
Output：4
问题分析：
这题说了每个货币可以无限次使用，可以把这题看做是一棵树，每个节点都有 n 个子节点，其中 n 是数组的长度，如下图所示。
到每个节点相当于选择一个货币，如果想要货币最少，只需要计算这棵树的最小深度即可。我们看到这棵树出现了大量的重复计算，也就是我们所说的重叠子问题，但我们依然可以使用备忘录的方式来解决。
public int minMoney(int[] coins, int amount) {
int res = minDepth(coins, amount, new int[amount + 1]);
return res == Integer.MAX_VALUE ? -1 : res;
}
private int minDepth(int[] coins, int amount, int[] map) {
if (amount == 0)
return 0;
if (map[amount] != 0)// 如果计算过直接从map中取。
return map[amount];
int min = Integer.MAX_VALUE;
for (int i = 0; i < coins.length; i++) {
if (amount < coins[i])
continue;
min = Math.min(min, minDepth(coins, amount - coins[i], map));
}
// 把计算的结果存储到map一份。
map[amount] = min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min + 1;
return map[amount];
}
使用备忘录相当于把重复的子树给剪掉，只保留一个。这题除了使用递归我们还可以使用动态规划，递归和动态规划的区别就是递归会把一个大的问题分解成一个个小的问题，如果没有备忘录的话每个小的问题都是独立计算的，因为小的问题有重叠，所以会造成大量重复计算。而动态规划是从小的问题开始逐步推导到一个大的问题。递归计算的时候是从叶子节点往上走的时候才开始计算的，相当于 N 叉树的后续遍历，他是从下往上计算的，我们常说递归是自顶往下是指问题的划分，他是把大的问题分成小的问题，然后小的问题单独计算。动态规划是自底往上是指问题的推导，从一个小的问题逐步推导一个大的问题，所以如果要求大的问题，必须要把小的问题给求出来。我们来看下这题使用动态规划该怎么解决。
定义 dp[i] 表示凑够金额为 i 所需要的货币数，假设我们知道从 dp[0] 到 dp[19] 中每一个数字所对应的最少货币数，那么 dp[20] 怎么求？很明显如果选择一个金额为 5 的货币，那么所需要的货币最少是 dp[20]=dp[15]+1 。同理选择金额为 2 和 3 的货币，所需要的货币最少分别为 dp[20]=dp[18]+1 和 dp[20]=dp[17]+1 。那么这 3 种货币我们应该选择哪种呢？当然选择所需货币最少的。
dp[20]=min(dp[15],dp[18],dp[17])+1;
根据上面的分析，如果要凑够金额为 i 所需要的最少货币，需要遍历所有面值的货币，这里还要注意所选择货币的金额一定不能大于 i ，所以我们可以得到下面的计算公式。
for (int j = 0; j < coins.length; j++) {// 遍历货币。
if (coins[j] <= i)
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
正如上面分析的那样，如果要计算 dp[20]，我们要知道 dp[0] 到 dp[19] 之间所有的值。所以这里如果要计算 dp[i] ，需要知道 dp[0] 到 dp[i-1] 之间所有的值。求 dp[i] 和 dp[i-1] 的原理实际上是一样的，只需要在外面套一个循环即可。
for (int i = 1; i <= amount; i++) {// 计算dp[0]到dp[i]的值。
for (int j = 0; j < coins.length; j++) {// 遍历货币
if (coins[j] <= i)
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
当 i 足够小的时候不需要计算，直接给他一个默认值，这就是动态规划中的边界条件。就像递归一样，当规模足够小的时候直接返回一个值，不需要在计算了。那么这题的边界条件是 dp[0] = 0 ，凑够金额为 0 所需要的货币是 0 ，我们来看下最终代码。
public int minMoney(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);// 默认个最大值。
dp[0] = 0;
for (int i = 1; i <= amount; i++) {// 计算dp[0]到dp[i]的值。
for (int j = 0; j < coins.length; j++) {// 遍历货币。
if (coins[j] <= i)
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
来思考一下，这里的两个 for 循环能不能互换，也就是外层遍历货币内层遍历金额 amount ，实际上是可以的，这样可以理解为前 i-1 种货币凑够金额为 amount 所需要的货币数，当我们在增加第 i 种货币的时候，判断凑够金额为 amount 所需要的货币数。
国王与金矿
有一个国家发现了 5 座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是 10 人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
第一座金矿含金 500 ，需要 5 人；第二座金矿含金 200 ，需要 3 人；第三座金矿含金 300 ，需要 4 人；第四座金矿含金 350 ，需要 3 人；第五座金矿含金 400 ，需要 5 人。
问题分析：
每个金矿都有两种选择，要么全挖要么不挖，不能只挖一部分，组合起来就会有 2^5 种选择，只需要枚举所有的组合，找出最大值即可，但要保证所选组合的人数不能超过 10 ，如下图所示。
如果我们不考虑人数是否够用的情况下，他就是一棵满二叉树，二叉树的左子节点表示挖，右子节点表示不挖。
/**
* @param totalWorker 总的工人数量
* @param index 金矿的索引，从 0 开始
* @param people 每个金矿开采所需的人数
* @param gold 每个金矿储量
* @return 最多收益
*/
private int getMostGold(int totalWorker, int index,
int[] people, int[] gold) {
// 如果没有工人了，或者金矿都挖完了，返回 0 。
if (totalWorker == 0 || index == people.length)
return 0;
// 不挖当前金矿所获得的最大收益。
int noDig = getMostGold(totalWorker, index + 1, people, gold);
// 如果人数不够，就不能挖当前金矿。
if (totalWorker < people[index])
return noDig;
// 挖当前金矿所获得的最大收益。
int dig = getMostGold(totalWorker - people[index], index + 1,
people, gold) + gold[index];
// 每个金矿要么挖要么不挖，我们选择收益最大的。
return Math.max(noDig, dig);
}
上面是使用递归的方式，复杂度比较高，是 2^n （ n 是金矿的数量），在图 11-6 中我们看到出现了大量重叠的子树，也就是出现大量重复的计算，一种方式可以使用备忘录把重复的给剪掉，我们来看另一种解决方式-动态规划。假设挖第一个金矿，就会用掉 5 个人，获得 500 金币，然后剩下 5 个人还可以在剩下的 4 个金矿中继续挖。如果我们不挖第一个金矿，就不能获得金币，但还有 10 个人，他们可以继续在剩下的 4 金矿中挖，这两种情况我们只需要取最大值即可，如下图所示。
我们定义二维数组 dp[i][j] 表示 i 个人挖前 j 个金矿获得的最大金币数，对于第 j 个金矿有两种选择。
- 如果不挖第
j个金矿，那么人数不会减少，金币也不会增加，所以dp[i][j]=dp[i][j-1]。也就是说i个人挖前j个金矿获得的最大金币数和i个人挖前j-1个金矿获得的最大金币数是一样的，因为第j个金矿没挖。 -
如果挖第
j个金矿（前提是人数要够），人数会减少p[j]，金币相应的也会增加g[j]，所以dp[i][j]=dp[i-p[j]][j-1]+g[j]。
递推公式如下：
if (i < p[j]) // 剩余人数如果小于当前金矿所需要的人数，则不能挖。
dp[i][j] = dp[i][j - 1];
else // 剩余人数不小于当前金矿所需要的人数，可以挖也可以不挖，取两者最大值。
dp[i][j] = Math.max(dp[i][j - 1], dp[i - p[j]][j - 1] + g[j]);
初始条件就是假设只有一个金矿，在人数小于当前金矿人数的时候是不能挖的，金币为 0 ，否则是可以挖的，金币为当前金矿的金币数。
private int getMostGold(int totalWorker, int[] p, int[] g) {
int[][] dp = new int[totalWorker + 1][p.length];
for (int i = 1; i <= totalWorker; i++) {
if (i >= p[0])// 大于等于当前金矿所需要的人数是才可以挖。
dp[i][0] = g[0];
}
for (int i = 1; i <= totalWorker; i++) {
for (int j = 1; j < p.length; j++) {
if (i < p[j])// 剩余人数如果小于当前金矿所需要的人数，则不能挖。
dp[i][j] = dp[i][j - 1];
else// 剩余人数不小于当前金矿所需要的人数，可以挖也可以不挖，取两者最大值。
dp[i][j] = Math.max(dp[i][j - 1], dp[i - p[j]][j - 1] + g[j]);
}
}
return dp[totalWorker][p.length - 1];
}
这里大家也可以尝试做一些优化，比如把二维数组变成一维数组，这里就不在介绍。
解题思路
通过前面的分析我们可以看到，动态规划解决的就是重复的子问题，如果一个解没有重复子问题，可以不使用动态规划，直接搜索即可。因为有重复子问题，动态规划就类似于有备忘录的搜索，他是从小的问题逐步推导到大的问题，所以我们需要知道他们之间的推导关系，这个推导关系就是递推公式。当问题足够小的时候，没法从更小的问题推导，直接给他一个默认值，这就是动态规划的边界条件，有的也叫 Base Case，有的也叫初始值。所以对于动态规划的题我们可以按照下面三个步骤来解：
1，定义 dp 数组表示的含义：常见的有 dp[] ， dp[][]， dp[][][]，很少出现四维及四维以上的数组。
2，找出递推公式：也就是数组之间的推导关系，从小的问题来推导大的问题，一般使用一个或多个 for 循环来计算。
3，找出初始值：初始值是不需要推导的，直接赋值。
这里的难点在于找出递推公式，递推公式找出之后计算当前状态值的时候，要确保在这之前的状态都已经计算完成，因为动态规划当前状态要依赖之前状态的结果，而之前状态结果是对历史的总结，计算之后不会在发生改变。
