当前位置:   article > 正文

【LeetCode刷题】新手一看就会的——动态规划详解—入门_运筹学动态规划解题思路

运筹学动态规划解题思路

目录

前言

什么是动态规划

动态规划基本思想

动态规划实例讲解

青蛙跳阶问题

带备忘录的递归解法(自顶向下)

自底向上的动态规划 

动态规划的解题套路

动态规划的解题思路

1. 穷举分析

2. 确定边界

3. 找规律,确定最优子结构

4, 写出状态转移方程

5. 代码实现


 

前言

我们刷leetcode的时候,经常会遇到动态规划类型题目。动态规划问题非常非常经典,也很有技巧性,一般大厂都非常喜欢问。动态规划算法我在刚接触算法设计时很苦恼的问题,对于相关类型题目,完全无从下手。之后就在网上看原理和讲解,在看了很多讲解和教程中,花了很多走了很多弯路之后,现在,总结一下比较重要以及以比较好理解的方式,一步一步讲解动态规划是怎样使用的,只有知道怎样使用,才能更好地理解,而不是一味地对概念和原理进行反复琢磨。文章如果有不正确的地方,欢迎大家指出哈,感谢感谢~

什么是动态规划

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。简单来说就是,通过把复杂的原问题分解为相对简单的子问题的方式去求解。动态规划常常适用于有重叠子问题最优子结构性质的问题。

一般这些子问题很相似,可以通过函数关系式递推出来。然后呢,动态规划就致力于解决每个子问题一次,减少重复计算,比如斐波那契数列就可以看做入门级的经典动态规划问题。

动态规划基本思想

基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。经分解得到子问题往往不是互相独立的。另外,求解子问题时,有些子问题被重复计算了很多次。而动态规划能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

总结上面:动态规划最核心的思想,分解原问题为子问题、记住过往、减少重复计算。

方便理解,我们联系一下网上比较流行的一个例子

  • A : "1+1+1+1+1+1+1+1 =?"
  • A : "上面等式的值是多少"
  • B : 计算 "8"
  • A : 在上面等式的左边写上 "1+" 呢?
  • A : "此时等式的值为多少"
  • B : 很快得出答案 "9"
  • A : "你怎么这么快就知道答案了"
  • A : "只要在8的基础上加1就行了"
  • A : "所以你不用重新计算,因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"

动态规划实例讲解

青蛙跳阶问题

问题描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。

对于没有动态规模刷题经验的小伙伴来说,看到这题可能有点不知从哪里下手,其实我们可以这样发散一下思路:

  • 要想跳到第10级台阶,要么是先跳到第9级,然后再跳1级台阶上去;要么是先跳到第8级,然后一次迈2级台阶上去。
  • 同理,要想跳到第9级台阶,要么是先跳到第8级,然后再跳1级台阶上去;要么是先跳到第7级,然后一次迈2级台阶上去。
  • 要想跳到第8级台阶,要么是先跳到第7级,然后再跳1级台阶上去;要么是先跳到第6级,然后一次迈2级台阶上去。

假设跳到第n级台阶的跳数我们定义为f(n),很显然就可以得出以下公式:

f(10) = f(9)+f(8)
f (9)  = f(8) + f(7)
f (8)  = f(7) + f(6)
...
f(3) = f(2) + f(1)

即通用公式为: f(n) = f(n-1) + f(n-2

那f(2) 或者 f(1) 等于多少呢?

  • 当只有2级台阶时,有两种跳法,第一种是直接跳两级,第二种是先跳一级,然后再跳一级。即f(2) = 2;
  • 当只有1级台阶时,只有一种跳法,即f(1)= 1;

因此可以用递归去解决这个问题:

  1. class Solution {
  2. public int numWays(int n) {
  3. if(n == 1){
  4. return 1;
  5. }
  6. if(n == 2){
  7. return 2;
  8. }
  9. return numWays(n-1) + numWays(n-2);
  10. }
  11. }

去leetcode提交一下,发现有问题,超出时间限制了

  • 要计算原问题 f(10),就需要先计算出子问题 f(9) 和 f(8)
  • 然后要计算 f(9),又要先算出子问题 f(8) 和 f(7),以此类推。
  • 一直到 f(2) 和 f(1),递归树才终止。

我们先来看看这个递归的时间复杂度吧:

递归时间复杂度 = 解决一个子问题时间*子问题个数
  • 一个子问题时间 = f(n-1)+ f(n-2),也就是一个加法的操作,所以复杂度是 O(1);
  • 问题个数 = 递归树节点的总数,递归树的总节点 = 2^n-1,所以是复杂度O(2^n)

因此,青蛙跳阶,递归解法的时间复杂度 = O(1) * O(2^n) = O(2^n),就是指数级别的,爆炸增长的,如果n比较大的话,超时很正常的了。

回过头来,你仔细观察这颗递归树,你会发现存在大量重复计算,比如 f (8)被计算了两次,f (7)被重复计算了3次...所以这个递归算法低效的原因,就是存在大量的重复计算

既然存在大量重复计算,那么我们可以先把计算好的答案存下来,即造一个备忘录,等到下次需要的话,先去备忘录查一下,如果有,就直接取就好了,备忘录没有才开始计算,那就可以省去重新重复计算的耗时啦!这就是带备忘录的解法。

带备忘录的递归解法(自顶向下)

一般使用一个数组或者一个哈希map充当这个备忘录

  • 第一步,f(10)= f(9) + f(8),f(9) 和f(8)都需要计算出来,然后再加到备忘录中,如下:

 

  • 第二步, f(9) = f(8)+ f(7),f(8)= f(7)+ f(6), 因为 f(8) 已经在备忘录中啦,所以可以省掉,f(7),f(6)都需要计算出来,加到备忘录中

  • 第三步, f(8) = f(7)+ f(6),发现f(8),f(7),f(6)全部都在备忘录上了,所以都可以剪掉。

 带备忘录的递归算法,子问题个数=树节点数=n,解决一个子问题还是O(1),所以带备忘录的递归算法的时间复杂度是O(n)。接下来呢,我们用带备忘录的递归算法去撸代码,解决这个青蛙跳阶问题的超时问题咯~,代码如下:

  1. public class Solution {
  2. //使用哈希map,充当备忘录的作用
  3. Map<Integer, Integer> tempMap = new HashMap();
  4. public int numWays(int n) {
  5. // n = 0 也算1种
  6. if (n == 0) {
  7. return 1;
  8. }
  9. if (n <= 2) {
  10. return n;
  11. }
  12. //先判断有没计算过,即看看备忘录有没有
  13. if (tempMap.containsKey(n)) {
  14. //备忘录有,即计算过,直接返回
  15. return tempMap.get(n);
  16. } else {
  17. // 备忘录没有,即没有计算过,执行递归计算,并且把结果保存到备忘录map中,对1000000007取余(这个是leetcode题目规定的)
  18. tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
  19. return tempMap.get(n);
  20. }
  21. }
  22. }

自底向上的动态规划 

动态规划跟带备忘录的递归解法基本思想是一致的,都是减少重复计算,时间复杂度也都是差不多。但是呢:

  • 带备忘录的递归,是从f(10)往f(1)方向延伸求解的,所以也称为自顶向下的解法。
  • 动态规划从较小问题的解,由交叠性质,逐步决策出较大问题的解,它是从f(1)往f(10)方向,往上推求解,所以称为自底向上的解法。

动态规划有几个典型特征,最优子结构、状态转移方程、边界、重叠子问题。在青蛙跳阶问题中:

  • f(n-1)和f(n-2) 称为 f(n) 的最优子结构
  • f(n)= f(n-1)+f(n-2)就称为状态转移方程
  • f(1) = 1, f(2) = 2 就是边界啦
  • 比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重叠子问题。

我们来看下自底向上的解法,从f(1)往f(10)方向,想想是不是直接一个for循环就可以解决啦,如下:

自底向上

台阶数123456...10
子结构f(1)f(2)f(3)f(4)f(5)f(6)...f(10)
跳法12f(1)+f(2)f(2)+f(3)f(3)+f(4)f(5)+f6)...f(8)+f(9)

带备忘录的递归解法,空间复杂度是O(n),但是呢,仔细观察上图,可以发现,f(n)只依赖前面两个数,所以只需要两个变量a和b来存储,就可以满足需求了,因此空间复杂度是O(1)

自底向上

台阶数123456...10
子结构f(1)f(2)f(3)f(4)f(5)f(6)...f(10)
跳法12f(1)+f(2)f(2)+f(3)f(3)+f(4)f(4)+f(5)...f(8)+f(9)
替换变量a=1b=2a=1+2=3b=2+3=5a=3+5=0b=5+8=13...b=a+b

动态规划实现代码如下:

  1. public class Solution {
  2. public int numWays(int n) {
  3. if (n<= 1) {
  4. return 1;
  5. }
  6. if (n == 2) {
  7. return 2;
  8. }
  9. int a = 1;
  10. int b = 2;
  11. int temp = 0;
  12. for (int i = 3; i <= n; i++) {
  13. temp = (a + b)% 1000000007;
  14. a = b;
  15. b = temp;
  16. }
  17. return temp;
  18. }
  19. }

动态规划的解题套路

什么样的问题可以考虑使用动态规划解决呢?

如果一个问题,可以把所有可能的答案穷举出来,并且穷举出来后,发现存在重叠子问题,就可以考虑使用动态规划。

比如一些求最值的场景,如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等,都是动态规划的经典应用场景。

动态规划的解题思路

动态规划的核心思想就是拆分子问题,记住过往,减少重复计算。 并且动态规划一般都是自底向上的,因此到这里,基于青蛙跳阶问题,我总结了一下我做动态规划的思路:

  • 穷举分析
  • 确定边界
  • 找出规律,确定最优子结构
  • 写出状态转移方程

1. 穷举分析

  • 当台阶数是1的时候,有一种跳法,f(1) =1
  • 当只有2级台阶时,有两种跳法,第一种是直接跳两级,第二种是先跳一级,然后再跳一级。即f(2) = 2;
  • 当台阶是3级时,想跳到第3级台阶,要么是先跳到第2级,然后再跳1级台阶上去,要么是先跳到第 1级,然后一次迈 2 级台阶上去。所以f(3) = f(2) + f(1) =3
  • 当台阶是4级时,想跳到第3级台阶,要么是先跳到第3级,然后再跳1级台阶上去,要么是先跳到第 2级,然后一次迈 2 级台阶上去。所以f(4) = f(3) + f(2) =5
  • 当台阶是5级时......

2. 确定边界

通过穷举分析,我们发现,当台阶数是1的时候或者2的时候,可以明确知道青蛙跳法。f(1) =1,f(2) = 2,当台阶n>=3时,已经呈现出规律f(3) = f(2) + f(1) =3,因此f(1) =1,f(2) = 2就是青蛙跳阶的边界。

3. 找规律,确定最优子结构

n>=3时,已经呈现出规律 f(n) = f(n-1) + f(n-2) ,因此,f(n-1)和f(n-2) 称为 f(n) 的最优子结构。什么是最优子结构?有这么一个解释:

一道动态规划问题,其实就是一个递推问题。假设当前决策结果是f(n),则最优子结构就是要让 f(n-k) 最优,最优子结构性质就是能让转移到n的状态是最优的,并且与后面的决策没有关系,即让后面的决策安心地使用前面的局部最优解的一种性质

4, 写出状态转移方程

通过前面3步,穷举分析,确定边界,最优子结构,我们就可以得出状态转移方程

5. 代码实现

我们实现代码的时候,一般注意从底往上遍历哈,然后关注下边界情况,空间复杂度,也就差不多啦。动态规划有个框架的,大家实现的时候,可以考虑适当参考一下:

  1. dp[0][0][...] = 边界值
  2. for(状态1 :所有状态1的值){
  3. for(状态2 :所有状态2的值){
  4. for(...){
  5. //状态转移方程
  6. dp[状态1][状态2][...] = 求最值
  7. }
  8. }
  9. }

最后,以上对动态规划的基本原理和案例进行分析,希望对正在学习动态规划的小伙伴们有帮助!如需要学习其他数据结构和算法请参考我的其他文章哦----》》》点击这里!!!

对大家学习有帮助的,记得点赞收藏哦!以免丢失!!!

 

参考:看一遍就理解:动态规划详解

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/622254
推荐阅读
相关标签
  

闽ICP备14008679号