动态规划算法
动态规划的英文名叫Dynamic Programming，是一种分阶段求解决策问题的数学思想。它不仅用于编程领域，也应用于管理学、经济学、生物学
总结一点就是大事化小，小事化了
题目：求楼梯阶数
有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
比如，每次走1级台阶，一共走10步，这是其中一种走法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。
再比如，每次走2级台阶，一共走5步，这是另一种走法。我们可以简写成 2,2,2,2,2。
当然，除此之外，还有很多很多种走法。
解决思路：
1. 假设你只差最后一步就走到第10级台阶，这时候会出现几种情况？
2. 两种情况
- 从9级走到10级
- 从8级走到10级
3. 想走到10级，最后一步必然是从8级或者9级开始的
4. 假设0-8级的台阶所有走法是x，0-9级所有台阶的走法是y ，那么走到10级的台阶总数就是x+y！
5. 为了方便表达，我们用式子表示： F（10） = F（9） + F（8）；
6. 以此类推： F（9） = F（8） + F（9） F（8） = F（7） + F（9）
上面的这种思想就是动态规划思想，将一个复杂的问题分阶段进行简化，一步一步简化成简单的问题，就是动态规划！
动态规划中包含三个重要的概念：
- 最优子结构 ：
F（9）和F（8） - 边界 ：只用一级台阶或者是2级台阶，可以直接得出结论，无需继续简化
F（1）和F（2） - 状态转移公式：
F（n）= F（n-1）+F（n-2）
求解方法：
1. 递归求解
public int getClimbingWays(int n){
if(n<1) return 0;
if(n == 1) return 1;
if(n == 2) return 2;
return getClimbingWays(n-1) + getClimbingWays(n-2);
}- 1
- 2
- 3
- 4
- 5
- 6
时间复杂度O（2^n）：
优化：有好些值被重复计算了
使用哈希表记录不同的计算结果，当遇到相同的参数时，不用计算，直接从哈希表中获取！
这种暂存计算结果的方式叫*备忘录算法*
- 2.
public int getClimbingWays(int n, HashMap<Integer,Integer> map){
if(n<1) return 0;
if(n == 1) return 1;
if(n == 2) return 2;
if(map.contains(n)){
return map.get(n);
}else{
int value = getClimbingWays(n-1) + getClimbingWays(n-2);
map.put(n,value);
return value;
}
}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
时间复杂度：n
空间复杂度：n
进一步优化代码：思路逆转过来，采用迭代的思维：
F（1） = 1
F（2） = 2
这是之前就确认过的结果
第一次迭代，台阶数等于3时，走法数量也为3，这个结果怎末来的，是F（1），F（2）这两个结果相加得到的，所以F（3）只依赖于F（1）和F（2）
第二次迭代，台阶数等于5时，走法数量也为3，这个结果怎末来的，是F（2），F（3）这两个结果相加得到的，所以F（4）只依赖于F（2）和F（3）
同理，由此可见，每一次迭代的过程总，只要保留之前的两个状态，就可以推导出新的状态，而不需要像备忘录那样保留全部的子状态
- 动态规划求解
public int getClimbingWays(int n){
if(n < 1) return 0;
if(n == 1) return 1;
if(n ==2 ) return 2;
int a = 1;
int b = 2;
int temp = 0;
for(int i=3; i<=n ; i++){
temp = a + b;
a = b;
b = temp;
}
return temp;
}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
题目二： 国王和金矿
有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
方法一：排列组合
每一座金矿都有挖与不挖两种选择，如果有N座金矿，排列组合起来就有2^N种选择。对所有可能性做遍历，排除那些使用工人数超过10的选择，在剩下的选择里找出获得金币数最多的选择。
代码比较简单就不展示了，时间复杂度也很明显，就是O(2^N)。
既然这道题属于动态规划，我们来看看属于动态规划的三个要素：对于这道题
最优子结构：题目要求出10个工人5个金矿时，挖最多黄金的选择，那么最有子结构应该就是
10个人四个金矿时的，挖黄金的最优
最优子结构和最终问题的关系：
5个金矿的最优选择，就是（4座金矿10个工人的挖金数量+第五座金矿的挖金数量）和 （前4座金矿10-第五座金矿人数+第五座金矿的挖金数量）
为了方便描述，我们把金矿数量设为N，工人数设为W，金矿的黄金数量设为数组G【】，金矿用工量设为数组p【】。
那么存在这样的关系：
F（5，10） =（ F（4，10），F（4，10-P【4】）+ G【4】））
边界：边界就是只有一座金矿，也就是N=1的时候，这时候没得选，只能挖这座唯一的金矿，得到的黄金数量就是G【0】；如果给定的工人数不够挖取第1座金矿的时候，也就是w