动态规划

简介: 动态规划(Dynamic Programming)是一种分阶段求解决策略问题的思想。动态规划中包含三个重要的概念:最优子结构   F(10)=F(8)+F(9)边界  n>=3 F(1)=1  F(2)=2状态转移公式  F(n)=F(n-1)+F(n-2) 题目:有一座高度是10级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。

动态规划(Dynamic Programming)是一种分阶段求解决策略问题的思想。

动态规划中包含三个重要的概念:

  1. 最优子结构   F(10)=F(8)+F(9)
  2. 边界  n>=3 F(1)=1  F(2)=2
  3. 状态转移公式  F(n)=F(n-1)+F(n-2) 

题目:

有一座高度是10级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。(此题是动态规划中最简单的问题,因为只有一个变化维度)

比如,每次走1级台阶,一共走10步,这是其中一种走法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。

再比如,每次走2级台阶,一共走5步,这是另一种走法。我们可以简写成 2,2,2,2,2。

解法一:暴力枚举,时间复杂度指数级,利用排列组合的思想,写一个多层嵌套循环遍历出所有可能。

解法二:动态规划。

问题建模:

假设现在你只差最后一步就走到第10级台阶,这时的情况有两种:

从9级走到10级

从8级走到10级

想走到第10级,最后一步必然是从8级或者9级开始。

如果已知0-9级台阶的走法有x种,0-8级台阶的走法有y种,那么0-10级台阶走法有几种?x+y。

F(10)=F(8)+F(9) -> F(n)=F(n-1)+F(n-2)  n>=3

F(1)=1  F(2)=2    

求解问题:

1.递归求解 

int getWay(int n){
  if(n<1) return 0;
  if(n==1) return 1;
  if(n==2) return 2;
  return geyWay(n-1)+getWay(n-2);        
}  

 时间复杂度,高度是n-1,节点数是2的n-1次方,复杂度近似O(2^N)。

备忘录算法:计算过程中可把计算过的n和结果存入hash,当遇到相同参数时直接获取。  复杂度O(N)。

2.迭代求解

递归是自顶向下做递归运算,迭代是自底向上做迭代推导。 空间复杂度O(1)

每一次迭代只需保留之前的两个状态就可以推导出新的状态,不需要像备忘录算法那样保存全部的子状态。

 

题目: 

有一个国家发现了5座金矿(500金/5人,200金/3人,300金/4人,350金/3人,400金/5人),每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。要求用程序求解出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿?

解法一:排列组合

每一座金矿都有挖与不挖两种选择,如果有N座金矿,排列组合起来就有2^N种选择。对所有可能性做遍历,排除那些使用工人数超过10的选择,在剩下的选择里找出获得金币数最多的选择。时间复杂度也很明显,就是O(2^N)。

解法二:动态规划

最优子结构:

如果第五个金矿选择不挖   10个工人5个金矿挖最多黄金->10个工人4个金矿挖最多黄金

如果第五个金矿选择挖      10个工人5个金矿挖最多黄金->(10-第五个金矿所需人数)个工人4个金矿挖最多黄金

状态转移公式:

10人5个金矿的最优选择就是10人4金矿的最优选择+(10-第五金矿所需人数)人4金矿的数量+第五金矿的挖金数量。

金矿数量设为N,工人数设为W,黄金量设为G[0-4],用工人量设为P[0-4]

5做金矿和4做金矿之间的最优选择之间存在的关系:

F(5,10)=MAX(F(4,10),F(4,10-P[4])+G[4])

边界:

N=1 W>=P[0]   得到黄金数量是F(N,W)=G[0]   

N=1  W<P[0]  得到黄金数量是F(N,W)=0     

最后的公式:

F(n,w) = 0    (n<=1, w<p[0]);

F(n,w) = g[0]     (n==1, w>=p[0]);

F(n,w) = F(n-1,w)    (n>1, w<p[n-1])  

F(n,w) = max(F(n-1,w),  F(n-1,w-p[n-1])+g[n-1])    (n>1, w>=p[n-1])

简单递归

把状态转移方程式翻译成递归程序,递归的结束的条件就是方程式当中的边界。因为每个状态有两个最优子结构,所以递归的执行流程类似于一颗高度为N的二叉树。 方法的时间复杂度是O(2^N)。

备忘录算法

在简单递归的基础上增加一个HashMap备忘录,用来存储中间结果。HashMap的Key是一个包含金矿数N和工人数W的对象,Value是最优选择获得的黄金数。 方法的时间复杂度和空间复杂度相同,都等同于备忘录中不同Key的数量。

迭代算法: 

表格第一列代表给定前1-5座金矿的情况,也就是N的取值。

表格的第一行代表给定的工人数,也就是W的取值。

表格其余空白的格子代表N和W对应的黄金获得数,也就是F(N,W)。

第一个金矿,400金/5人  第一行其实就是刚才分析的边界,因此可直接得出结果。

 

第二个金矿,500金/5人 

前四个格子由于人数小于5人,所以是0。

W>=5   F(1,w)=400 p[0]=5 g[0]=500  F(1,w-p[0])=[0-400]->W=10的时候还剩5个人还能挖400

F(2,w) = max(F(1,w),  F(1,w-p[0])+g[0])  

最终表格:

除了第一行以外,每个格子都是前一行的一个或两个格子推导而来。

所以可以只缓存前一行的结果,推导出新的一行。方法的时间复杂度是 O(n * w),空间复杂度是(w)。

和工人数W成正比,递归算法的话只与N有关系,当工人数为1000时,迭代算法并不比递归算法性能好。

 

目录
相关文章
|
7月前
|
算法 测试技术 C++
|
7月前
|
机器人 NoSQL 容器
动态规划一
动态规划一
|
7月前
动态规划1
动态规划1
43 0
动态规划1
|
存储
【动态规划】
【动态规划】
|
7月前
动态规划
动态规划
61 0
|
机器学习/深度学习 算法
动态规划详解
前段时间一直在做关于数据结构的题,也算是对数据结构有了一定的了解,知道了有些数据结构的基本算法。现在刚刚开始接触动态规划,其实写这篇文章的初衷是一来锻炼一下自己的总结能力,二来也是希望通过这篇文章,来指引和我一样的初学者,废话不多说了,开始吧。
61 0
|
定位技术
动态规划题:夺宝奇兵
动态规划题:夺宝奇兵
93 0
|
人工智能
动态规划的证明题
动态规划的证明题
115 0
|
机器学习/深度学习
朝题夕解之动态规划(4)
朝题夕解之动态规划(4)
122 0
朝题夕解之动态规划(4)
|
机器学习/深度学习
朝题夕解之动态规划(7)
朝题夕解之动态规划(7)
136 0
朝题夕解之动态规划(7)