当前位置: 首页 > news >正文

动态规划,这将是你见过最详细的讲解

文章目录

  • 一、为什么要讲动态规划呢?
  • 二、什么是动态规划
  • 三、感受一下递归算法、备忘录算法、动态规划
    • 递归算法
    • 带备忘录的递归解法(自定向下)
    • 自底向上的动态规划
  • 四、动态规划的解题套路
    • 1. 穷举分析
    • 2. 确定边界
    • 3. 确定最优子结构
    • 4. 写出状态转移方程

我建议直接看下面的参考文章,因为大佬的讲解非常到位,我这里做的笔记肯定是没那么详细的,这里只是给我自己做个记录

看一遍就理解:动态规划详解
算法-动态规划 Dynamic Programming–从菜鸟到老鸟

一、为什么要讲动态规划呢?

我们刷leetcode的时候,经常会遇到动态规划类型题目。动态规划问题非常非常经典,也很有技巧性,一般大厂都非常喜欢问。学就要学一些回报最大的知识

二、什么是动态规划

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

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

相信看到这里,我们可以知道动态规划也用到HashMap集合,如果还不会,请看我另一篇博客,让你秒懂Java集合框架

动态规划核心思想
动态规划最核心的思想,就在于拆分子问题,记住过往,减少重复计算。然而我认为记不记住过往不重要,重要的是不要重复计算子问题就行了。例如自顶向下就需要备忘录,自底向上就不需要备忘录了。
在这里插入图片描述
我们来看下,网上比较流行的一个例子

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),很显然就可以得出以下公式:

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)

我们现在确定一下界限

通常设为为0和1,但是0代表还没有上阶梯,所以要从1开始。再根据公式f(n) = f(n-1) + f(n-2),可以知道界限需要设为1,2,并且f(1) = 1,f(2) = 2.

递归算法

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(n-1)+f(n-2),也就是一个加法的操作,所以复杂度是 O(1);
问题个数 = 递归树节点的总数,递归树的总节点 = 2n-1,所以是复杂度O(2n)。

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

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

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

一般使用一个数组或者一个哈希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);}}
}

自底向上的动态规划

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

带备忘录的递归,是从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)就是重叠子问题。
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) 的最优子结构。什么是最优子结构?有这么一个解释:

4. 写出状态转移方程

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

相关文章:

动态规划,这将是你见过最详细的讲解

文章目录一、为什么要讲动态规划呢&#xff1f;二、什么是动态规划三、感受一下递归算法、备忘录算法、动态规划递归算法带备忘录的递归解法&#xff08;自定向下&#xff09;自底向上的动态规划四、动态规划的解题套路1. 穷举分析2. 确定边界3. 确定最优子结构4. 写出状态转移…...

【服务器数据恢复】FreeNAS层UFS2文件系统数据恢复案例

服务器数据恢复环境&#xff1a; Dell存储服务器&#xff0c;采用esxi虚拟化系统&#xff0c;esxi虚拟化系统里有3台虚拟机&#xff1b;上层iSCSI使用FreeNAS构建&#xff0c;通过iSCSI方式实现FCSAN功能&#xff1b;FreeNAS层采用UFS2文件系统。 esxi虚拟化系统里有3台虚拟机中…...

Zookeeper安装和基本使用

目录标题一、下载二、安装三、启动客户端测试四、使用zk一、下载 注意&#xff1a;自zk3.5.5版本以后&#xff0c;已编译的jar包&#xff0c;尾部有bin&#xff0c;应该使用的是apache-zookeeper-3.8.0-bin.tar.gz。&#xff0c;因此在下载高版本时&#xff0c;因该下载后缀带b…...

字节面试惨败,闭关修炼再战美团(Android 面经~)

作者&#xff1a;王旭 前言 本人从事Android 开发已经有5年了&#xff0c;受末日寒气影响&#xff0c;被迫在家休整&#xff0c;事后第一家选择字节跳动面试&#xff0c;无奈的被面试官虐得“体无完肤”&#xff0c;好在自己并未气馁&#xff0c;于是回家开始回家进行闭关修炼…...

【机器学习实战】七、梯度下降

梯度下降 一、线性回归 线性回归算法推导过程可以基于最小二乘法直接求解&#xff0c;但这并不是机器学习的思想&#xff0c;由此引入了梯度下降方法。本文讲解其中每一步流程与实验对比分析。 1.初始化 import numpy as np import os %matplotlib inline import matplotli…...

什么是极速文件传输,极速文件传输如何进行大文件传输

当谈到大文件传输时&#xff0c;人们总是担心大数据文件的大小以及将它们从一个位置交换到另一个位置需要多长时间。由于数据捕获高分辨率视频和图像的日益复杂&#xff0c;文件的大小不断增加。数据工作流在地理上变得越来越分散。在一个位置生成的文件在其他位置处理或使用。…...

Spring Boot 日志

目录 1.概述 2.切换日志实现 3.使用 3.1.日志级别 3.3.日志离线 3.4.详细定制 1.概述 由一些历史原因&#xff0c;JAVA领域存在有很多日志框架&#xff0c;如Log4j、Logback、log4j2。 log4j是Java日志框架的元老&#xff0c;在log4j被Apache Foundation收入门下之后&a…...

好用的研发管理看板工具有哪些?10款主流看板管理软件盘点

10大企业看板工具软件&#xff1a;1.软件开发项目看板 PingCode&#xff1b;2.通用看板软件 Worktile&#xff1b;3.开源看板软件 Wekan&#xff1b;4.免费看板软件 Trello&#xff1b;5.个人和小团队的看板软件 Todoist &#xff1b;6.开源免费看 Kanboard&#xff1b;7.面向个…...

【软考系统架构设计师】2022下案例分析历年真题

【软考系统架构设计师】2022下案例分析历年真题 【软考系统架构设计师】2022下案例分析历年真题【软考系统架构设计师】2022下案例分析历年真题2022下案例分析历年真题第一题&#xff08;25分&#xff09;2022下案例分析历年真题第二题&#xff08;25分&#xff09;2022下案例分…...

Java skill - @JsonAlias 和 @JsonProperty

Java skill - JsonAlias 和 JsonPropertyJava skill系列目录&#xff1a;JsonAlias 和 JsonProperty使用 JsonProperty 的麻烦场景&#xff1a;使用 JsonAlias 应对麻烦场景&#xff1a;Java skill系列目录&#xff1a; 【Java skill - 统计耗时用StopWatch】 【Java skill - …...

【实际开发18】- 静态 3

目录 1. 调试与评估 2. 单元测试的管理 1. 单元测试的文档 3. 系统集成的模式与方法 1. 集成测试前的准备 2. 集成测试的模式 3. 大棒集成方法 ( Big-bang Integration) 4. 自顶向下和自底向上集成方法 1. 自顶向下法 ( Top-down Integration ) 2. 自底向上法 ( Bott…...

【swagger2】开发api文档

文章目录一、swagger2 简介背景Open API ???swagger2的作用swagger2常用工具组件&#xff1a;二、Springfox三、springBoot使用swagger2&#xff08;简单示例&#xff09;四、Swagger-UI使用五、配置文件1、配置类&#xff1a;给docket上下文配置api描述信息2、配置类&#…...

Github 上如何提交 pull request

什么是复刻&#xff08;forking&#xff09;? 我们可以通过复刻操作将喜爱的仓库保存自己的Github账户中&#xff0c;以便独立地对其进行操作。 通过复刻&#xff0c;我们可以得到包含完整版本历史的目标仓库的实例&#xff0c;之后可以对复刻得到的仓库进行任意操作而不会影响…...

Redis面试知识

概述 Redis 是速度非常快的非关系型(NoSQL)内存键值数据库,可以存储键和五种不同类型的值之间的映射。 键的类型只能为字符串,值支持五种数据类型:字符串、列表、集合、散列表、有序集合。 Redis 支持很多特性,例如将内存中的数据持久化到硬盘中,使用复制来扩展读性能…...

Spring面试重点(四)——Spring事务

Spring事务 事务的方式 spring中使用事务有两种方式&#xff0c;一种是编程式事务&#xff0c;一种是声明式事务。编程式事务推荐使用TransactionTemplate&#xff0c;实现TransactionCallback接口&#xff0c;需要编码实现&#xff1b;声明式事务只需要在函数增加注解Transa…...

♡ — MySQL 存储引擎

MySQL 存储引擎架构 MySQL 存储引擎采用的是插件式架构&#xff0c;支持多种存储引擎&#xff0c;我们甚至可以为不同的数据库设置不同的存储引擎以适应不同场景的需要&#xff1b;存储引擎是基于表的&#xff0c;而不是数据库。 MyISAM 和 InnoDB 的区别 MySQL 5.5 之前&am…...

大数据技术架构(组件)34——Spark:Spark SQL--Optimize

2.2.3、Optimize2.2.3.1、SQL3.3.1.1、RB1、Join选择在Hadoop中&#xff0c;MR使用DistributedCache来实现mapJoin。即将小文件存放到DistributedCache中&#xff0c;然后分发到各个Task上&#xff0c;并加载到内存中&#xff0c;类似于Map结构&#xff0c;然后借助于Mapper的迭…...

Zookeeper实现分布式锁

文章目录ZK节点类型watch监听机制Zookeeper实现分布式锁锁原理创建锁的过程释放锁的过程ZK锁的种类代码实现Zookeeper是一个开源的分布式协调服务&#xff0c;是一个典型的分布式数据一致性解决方案。 分布式应用程序可以基于Zookeeper实现诸如数据发布/订阅&#xff0c;负载均…...

MFC 添加重新启动管理器支持

重启管理器是添加到 Visual Studio for Windows Vista 或更高版本操作系统的功能 如果发生意外关闭或重启&#xff0c;重新启动管理器将为你的应用程序添加支持。 重新启动管理器的行为取决于应用程序的类型。 如果你的应用程序是文档编辑器&#xff0c;则重新启动管理器让应用…...

一文带你深刻的进入Python,并且了解Python的优缺点

最近几年Python被吹的神乎其神&#xff0c;很多同学都不清楚Python到底能干什么&#xff1f;就盲目去学习Python,今天我就Python的应用领域来简单盘点一下&#xff0c;让想学习Python 的同学找对方向不迷茫。 2. Python 的特点 这里就谈谈自己的看法&#xff0c;首先 Python是…...

别具一格,原创唯美浪漫情人节表白专辑,(复制就可用)(html5,css3,svg)表白爱心代码(4)

别具一格,独此一家&#xff0c;原创唯美浪漫情人节表白专辑 不一样的惊喜哦~&#xff01;&#xff08;html5,css3,svg)表白爱心代码&#xff08;复制就可用&#xff09;&#xff08;4&#xff09; 目录 款式四&#xff1a;时光的记忆款 1、拷贝完整源代码 2、更新时光盒所…...

编译原理—翻译方案、属性栈代码

系列文章戳这里&#x1f447; 什么是上下文无关文法、最左推导和最右推导如何判断二义文法及消除文法二义性何时需要消除左递归什么是句柄、什么是自上而下、自下而上分析什么是LL(1)、LR(0)、LR(1)文法、LR分析表LR(0)、SLR(1)、LR(1)、LALR(1)文法之间的关系编译原理第三章习…...

链表

一、从尾到头打印链表题目&#xff1a;输入一个链表&#xff0c;按链表从尾到头的顺序返回一个ArrayList。解题思路&#xff1a;使用栈作为中转&#xff0c;可以实现倒置打印classSolution { public:vector<int> printListFromTailToHead(ListNode* head){//使用栈完成中…...

CSS 样式优先级

CSS 样式优先级决定了最终呈现在浏览器中的样式是哪一组样式&#xff0c;在多组样式中有冲突时&#xff0c;最终呈现在浏览器中的样式是具有最高优先级的样式。 CSS 样式优先级顺序如下&#xff1a; 内联样式 > 内部样式 > 外部样式 !important > 内联样式 > ID…...

SpingMVC获取请求参数

通过ServletAPI获取请求参数将HttpServletRequest作为控制器方法的形参&#xff0c;此时HttpServletRequest类型的参数表示封装了当前请求的请求报文的对象。html<form th:action"{/param/servletAPI}" method"post">用户名&#xff1a;<input ty…...

微搭使用笔记(二)微搭低代码平台介绍及基础使用

概述 官网地址&#xff1a; 官网 官方文档&#xff1a; 官方文档 FAQ: FAQ 腾讯云微搭低代码是一个高性能的低代码开发平台&#xff0c;用户可通过拖拽式开发&#xff0c;可视化配置构建 PC Web、H5 和小程序应用。支持打通企业内部数据&#xff0c;轻松实现企业微信管理、工…...

CountDownLatch的定义、使用 、原理

一、定义 CountDownLatch的作用很简单&#xff0c;就是一个或者一组线程在开始执行操作之前&#xff0c;必须要等到其他线程执行完才可以。我们举一个例子来说明&#xff0c;在考试的时候&#xff0c;老师必须要等到所有人交了试卷才可以走。此时老师就相当于等待线程&#xff…...

《Terraform 101 从入门到实践》 Terraform在公有云Azure上的应用

《Terraform 101 从入门到实践》这本小册在南瓜慢说官方网站和GitHub两个地方同步更新&#xff0c;书中的示例代码也是放在GitHub上&#xff0c;方便大家参考查看。 简介 Azure是微软的公有云&#xff0c;它提供了一些免费的资源&#xff0c;具体可以查看&#xff1a; https:/…...

别具一格,原创唯美浪漫情人节表白专辑,(复制就可用)(html5,css3,svg)表白爱心代码(3)

别具一格&#xff0c;原创唯美浪漫情人节表白专辑&#xff0c; (复制就可用)&#xff08;html5,css3,svg)表白爱心代码(3) 目录 款式三&#xff1a;心形实时显示认识多长时间桃花飞舞&#xff08;猫咪&#xff09;款 1、拷贝完整源代码 2、拷贝完整js代码 3、修改时间 4、…...

Linux 删除修改日期大于某一天的文件

在服务器运维过程中,我们往往会产生大量的日志文件. 如果日志文件命名能看出日志产生的时间,这些文件是很好删除的. 但有时,我们可能有成千上万的没有命名规律日志文件 下面的方法可以根据日志最后修改时间 批量删除这些文件 先给出完整命令: find /mydir -mtime 10 -name &…...