设为首页 加入收藏

TOP

动态规划的解题套路leetcode案例分析(一)
2023-07-23 13:27:25 】 浏览:252
Tags:解题套 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),很显然就可以得出以下公式:

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

第三步, 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提交一下,如图,稳了:

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

自底向上的动态规划

动态规划跟带备忘录的递归解法基本思想是一致的,都是减少重复计算,

首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇浅谈PHP设计模式的迭代器模式 下一篇多商户商城系统功能拆解18讲-平台..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目