ToB企服应用市场:ToB评测及商务社交产业平台

标题: 动态规划的解题套路leetcode案例分析 [打印本页]

---

作者: 莫张周刘王    时间: 2022-9-5 15:57
标题: 动态规划的解题套路leetcode案例分析
今天我们来讲解leetcode案例分析，如何动态规划的解题套路，态规划的核心思想，以前经常会遇到动态规划类型题目。动态规划问题非常非常经典，也很有技巧性，一般大厂都非常喜欢问。下面一起来学习动态规划的套路，文章要有不正确的地方，欢迎大家来吐槽，感谢感谢~

• 什么是动态规划？
  
• 动态规划的核心思想
  
• 一个例子走进动态规划
  
• 动态规划的解题套路
  
• leetcode案例分析
  

公众号：捡田螺的小男孩
什么是动态规划？

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

以上定义来自维基百科，看定义感觉还是有点抽象。简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

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

动态规划核心思想

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

我们来看下，网上比较流行的一个例子：

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

一个例子带你走进动态规划 -- 青蛙跳阶问题

暴力递归

leetcode原题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。

有些小伙伴第一次见这个题的时候，可能会有点蒙圈，不知道怎么解决。其实可以试想：

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

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

1. f（10） = f（9）+f(8)
2. f (9)  = f(8) + f(7)
3. f (8)  = f(7) + f(6)
4. ...
5. f(3) = f(2) + f(1)
7. 即通用公式为: 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），递归树才终止。
  

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

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)。接下来呢，我们用带备忘录的递归算法去撸代码，解决这个青蛙跳阶问题的超时问题咯~，代码如下：
[code]public class Solution {    //使用哈希map，充当备忘录的作用    Map tempMap = new HashMap();    public int numWays(int n) {        // n = 0 也算1种        if (n == 0) {            return 1;        }        if (n

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4