写点什么

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

  • 2021 年 11 月 12 日
  • 本文字数:4715 字

    阅读完需:约 15 分钟

  • 要想跳到第 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;


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


class?Solution?{


public?int?numWays(int?n)?{


if(n?==?1){


return?1;


}


if(n?==?2){


return?2;


}


return?numWays(n-1)?+?numWays(n-2);


}


}


去 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)都需要计算出来,加到备忘录中~



【一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


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



所以呢,用了备忘录递归算法,递归树变成光秃秃的树干咯,如下:



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


public?class?Solution?{


//使用哈希 map,充当备忘录的作用


Map<Integer,?Integer>?tempMap?=?new?HashMap();


public?int?numWays(int?n)?{


//?n?=?0?也算 1 种


if?(n?==?0)?{


return?1;


}


if?(n?<=?2)?{


return?n;


}


//先判断有没计算过,即看看备忘录有没有


if?(tempMap.containsKey(n))?{


//备忘录有,即计算过,直接返回


return?tempMap.get(n);


}?else?{


//?备忘录没有,即没有计算过,执行递归计算,并且把结果保存到备忘录 map 中,对 1000000007 取余(这个是 leetcode 题目规定的)


tempMap.put(n,?(numWays(n?-?1)?+?numWays(n?-?2))?%?1000000007);


return?tempMap.get(n);


}


}


}


去 leetcode 提交一下,如图,稳了:



其实,还可以用动态规划解决这道题。

自底向上的动态规划

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


  • 带备忘录的递归,是从 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 循环就可以解决啦,如下:



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



动态规划实现代码如下:


public?class?Solution?{


public?int?numWays(int?n)?{


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)%?1000000007;


a?=?b;


b?=?temp;


}


return?temp;


}


}

动态规划的解题套路

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



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




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

动态规划的解题思路

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


  • 穷举分析

  • 确定边界

  • 找出规律,确定最优子结构

  • 写出状态转移方程

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. 代码实现

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


dp[0][0][...]?=?边界值


for(状态 1 :所有状态 1 的值){


for(状态 2 :所有状态 2 的值){


for(...){


//状态转移方程


dp[状态 1][状态 2][...]?=?求最值


}


}


}

leetcode 案例分析

我们一起来分析一道经典 leetcode 题目吧




给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。




示例 1:


输入:nums =?[10,9,2,5,3,7,101,18]


输出:4


解释:最长递增子序列是?[2,3,7,101],因此长度为 4 。


示例 2:


输入:nums =?[0,1,0,3,2,3]


输出:4


我们按照以上动态规划的解题思路,


  • 穷举分析

  • 确定边界

  • 找规律,确定最优子结构

  • 状态转移方程

1.穷举分析

因为动态规划,核心思想包括拆分子问题,记住过往,减少重复计算。 所以我们在思考原问题:数组 num[i]的最长递增子序列长度时,可以思考下相关子问题,比如原问题是否跟子问题 num[i-1]的最长递增子序列长度有关呢?

自底向上的穷举

这里观察规律,显然是有关系的,我们还是遵循动态规划自底向上的原则,基于示例 1 的数据,从数组只有一个元素开始分析。


  • 当 nums 只有一个元素 10 时,最长递增子序列是[10],长度是 1.

  • 当 nums 需要加入一个元素 9 时,最长递增子序列是[10]或者[9],长度是 1。

  • 当 nums 再加入一个元素 2 时,最长递增子序列是[10]或者[9]或者[2],长度是 1。

  • 当 nums 再加入一个元素 5 时,最长递增子序列是[2,5],长度是 2。

  • 当 nums 再加入一个元素 3 时,最长递增子序列是[2,5]或者[2,3],长度是 2。

  • 当 nums 再加入一个元素 7 时,,最长递增子序列是[2,5,7]或者[2,3,7],长度是 3。

  • 当 nums 再加入一个元素 101 时,最长递增子序列是[2,5,7,101]或者[2,3,7,101],长度是 4。

  • 当 nums 再加入一个元素 18 时,最长递增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],长度是 4。

  • 当 nums 再加入一个元素 7 时,最长递增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],长度是 4.

分析找规律,拆分子问题

通过上面分析,我们可以发现一个规律


如果新加入一个元素 nums[i], 最长递增子序列要么是以 nums[i]结尾的递增子序列,要么就是 nums[i-1]的最长递增子序列。看到这个,是不是很开心,nums[i]的最长递增子序列已经跟子问题 nums[i-1]的最长递增子序列有关联了。


原问题数组 nums[i]的最长递增子序列?=?子问题数组 nums[i-1]的最长递增子序列/nums[i]结尾的最长递增子序列


是不是感觉成功了一半呢?但是如何把 nums[i]结尾的递增子序列也转化为对应的子问题呢?要是 nums[i]结尾的递增子序列也跟 nums[i-1]的最长递增子序列有关就好了。又或者 nums[i]结尾的最长递增子序列,跟前面子问题 num[j](0=<j<i)结尾的最长递增子序列有关就好了,带着这个想法,我们又回头看看穷举的过程:



nums[i]的最长递增子序列,不就是从以数组 num[i]每个元素结尾的最长子序列集合,取元素最多(也就是长度最长)那个嘛,所以原问题,我们转化成求出以数组 nums 每个元素结尾的最长子序列集合,再取最大值嘛。哈哈,想到这,我们就可以用 dp[i]表示以 num[i]这个数结尾的最长递增子序列的长度啦,然后再来看看其中的规律:



其实,nums[i]结尾的自增子序列,只要找到比 nums[i]小的子序列,加上 nums[i] 就可以啦。显然,可能形成多种新的子序列,我们选最长那个,就是 dp[i]的值啦




  • nums[3]=5,以5结尾的最长子序列就是[2,5],因为从数组下标0到3遍历,只找到了子序列[2]5小,所以就是[2]+[5]啦,即dp[4]=2



  • nums[4]=3,以3结尾的最长子序列就是[2,3],因为从数组下标0到4遍历,只找到了子序列[2]3小,所以就是[2]+[3]啦,即dp[4]=2



  • nums[5]=7,以7结尾的最长子序列就是[2,5,7][2,3,7],因为从数组下标0到5遍历,找到2,5和3都比 7 小,所以就有[2,7],[5,7],[3,7],[2,5,7]和[2,3,7]这些子序列,最长子序列就是[2,5,7]和[2,3,7],它俩不就是以5结尾和3结尾的最长递增子序列+[7]来的嘛!所以,dp[5]=3 =dp[3]+1=dp[4]+1





很显然有这个规律:一个以 nums[i]结尾的数组 nums


  • 如果存在 j 属于区间[0,i-1],并且 num[i]>num[j]的话,则有:


dp(i) =max(dp(j))+1,

最简单的边界情况

当 nums 数组只有一个元素时,最长递增子序列的长度 dp(1)=1,当 nums 数组有两个元素时,dp(2) =2 或者 1, 因此边界就是 dp(1)=1。

确定最优子结构

从穷举分析,我们可以得出,以下的最优结构:


dp(i)?=max(dp(j))+1,存在 j 属于区间[0,i-1],并且 num[i]>num[j]。


max(dp(j)) 就是最优子结构。

状态转移方程

评论

发布
暂无评论
看一遍就理解:动态规划详解