Comment on page
动态规划（Dynamic Programming）
动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。
区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。
其实就是说，动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决从而 得到更小的运行时间。
即用动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。
将 动态规划 的概念关键点抽离出来描述就是这样的：
- 动态规划法试图只解决每个子问题一次。
- 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。
下面通过爬楼梯问题来分析使用动态规划的解决问题（该问题也是在现场面试中遇到的）。
问题描述：爬楼梯，我们每次可以走 1 级阶梯或者 2 级阶梯，那我们走 50（n） 级阶梯总共有多少种走法。 在现场思考过程中，如果没有使用动态规划的话，那就要用递归的概念去做。
我们在高中的数学课里面应该学习过规律推理，那我们可以很容易的去推理出来公式： 1 级台阶： 1 种走法（f(1)） 2 级台阶： 2 种走法（f(2)） 3 级台阶： 3 种走法（f(3) = f(2) + f(1)） 4 级台阶： 5 种走法（f(4) = f(3) + f(2)） 5 级台阶： 8 种走法（f(5) = f(4) + f(3)） ... n 级台阶： f(n) = f(n-1) + f(n-2) （n > 2）
通过以上公式，很容易推导出一下递归代码：
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
code:
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
// a 保存倒数第二个子状态数据，b 保存倒数第一个子状态数据， temp 保存当前状态的数据
int a = 1, b = 2;
int temp = a + b;
for (int i = 3; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return temp;
}
还是以爬台阶为例，如果以递归的方式解决的话，那么这种方法的时间复杂度为O(2^n)
动态规划中包含三个重要的概念：
- 最优子结构
- 边界
- 状态转移公式
在爬台阶问题中：
f(10) = f(9) + f(8) 是最优子结构 f(1) 与 f(2) 是边界 f(n) = f(n-1) + f(n-2) 状态转移公式
爬台阶问题只是动态规划中相对简单的问题，因为它只有一个变化维度，如果涉及多个维度的话，那么问题就变得复杂多了。
难点就在于找出动态规划中的这三个概念。感觉跟我们高中学习的推理证明题有点像，通过现在的条件推断出结果。
有一个国家发现了 5 座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是 10 人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
Last modified 3yr ago