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

算法通关村 | 透彻理解动态规划

1. 斐波那契数列

1,1,2,3,5,8,13,..... f(n) = f(n-1) + f(n-2)

代码实现

    public static int count_2 = 0;public int fibonacci(int n){if (n <= 2){count_2++;return n;}int f1 = 1;int f2 = 2;int sum = 0;for (int i = 3; i < n; i++) {count_2++;sum = f1 + f2;f1 = f2;f2 = sum;}return sum;}

当n=20时,count是21891次,当n=30的时候结果是2692537,接近270万,为什么这么高,因为里面存在大量的循环,下面图中,n=8时,f(6)就重复计算两次,很多结点会被重复计算。

如何将其优化减少重复计算,这也是下面推导动态规划需要考虑的,可以将计算结果保存到数组中,f(n)的值保存在数组中,f(n)=arr[n],某个位置已经被计算出来,下次需要的时候直接取出来,不需要再递归。

    public static int[] arr = new int[50];public static int count_3 = 0;public static void main(String[] args) {Arrays.fill(arr,-1);arr[0] = 1;System.out.println(fibonacci(31));}static int fibonacci(int n){if (n == 2 || n == 1){count_3++;arr[n] = n;return n;}if (arr[n] != -1){count_3++;return arr[n];}else {count_3++;arr[n] = fibonacci(n - 1) + fibonacci(n - 2);return arr[n];}}

2 路径连环炮

文中的动态规划我们简称DP,路径相关的问题来分析动态规划,路径问题易于画图,方便理解,循序渐进的理解DP

2.1 第一炮:基本问题统计路径总数

LeetCode62 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

第一炮,我们研究如何通过递归来解决此问题,如下图所示,从起点开始要么向右,要么向下,每一种否会导致剩下的区间减少了一列或一行,形成两个不同区间的过程,每个区间继续以红点为起点继续上述操作,所以这就是一个递归的过程,

从图中寻找规律,目标从起点到终点,只能向右或向下,

1. 向右走一步,起点下面灰色的不会再被访问,后面剩一个3X1的矩阵,只能一直往下走,只有一种路径,

2. 向下走一步,起点右侧不不能再被访问,剩一个2X2的矩阵,还剩两种路径,

这是3X2的矩阵,一共有3中路径,一个2X2的矩阵和3X1的矩阵路径之和。

同样我们推导一个3X3的矩阵,就是一个3X2的矩阵和2X3的路径之和,

所以,对于一个mxn的矩阵,求路径的方法是serch(m,n)=search(m-1,n)+search(m,n-1);

    public int uniquePath(int m,int n){return search(m,n);}private int search(int m, int n) {if (m == 1 || n == 1){return 1;}return search(m-1,n) + search(m,n-1);}

对于3X3的矩阵,我们可以用二叉树表示

我们可以发现,和文章开头我们提到的一样,中间有重复计算,1,1计算了两次,那么如何优化

2.2 第二炮:使用二维数组优化递归

我们知道上面出现了重复计算,{1,1}出现两次,在{1,1}位置处,不管是从{0,1}还是{1,0}到来,都会产生两种走法,我们可以用二维数组记忆化搜索就不用两次遍历了,

每个格子都表示从起点开始到当前的位置有几种方式,这样我们通过计算路径的时候可以先查下二维数组有没有记录,有就直接读,没有再计算,这样就可以避免大量的重复计算,这就是记忆化搜索。

从上面的分析我们得到两个规律:

1.第一行和第一列都是1.

2.其他格子的值都是其左侧和上方格子之和,对于mXn的格子都适应。

    public int uniquePath(int m, int n){int[][] f = new int[m][n];f[0][0] = 1;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (i > 0 && j > 0){f[i][j] = f[i -1][j] + f[i][j -1];}else if (i > 0){f[i][j] = f[i -1][j];} else if (j > 0) {f[i][j] = f[i][j -1];}}}return f[m -1][n -1];}

2.3 第三炮:滚动数组:用一维代替二维数组

第三炮,我们通过滚动数组来优化此问题,上面缓存空间使用二维数组,占据空间大,能否进一步优化,我们看上面的二维数组找出规律。

发现除了第一行和第一列都是1外,每个位置都是其左侧和上方的格子之和,可以用一个大小为n的一维数组来解决:

将几个一维数组拼接起来,就是和上面的二维数组完全一样的,反复更新数组的策略就是滚动数组,计算公式是:dp[j] = dp[j]+dp[j-1]

    public int uniquePaths(int m, int n){int[] dp = new int[n];//将数组初始元素初始为1Arrays.fill(dp,1);for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {//等式左边的dp[j]是上一次计算后的,再加上左边的dp[j-1]即为当前结果dp[j] = dp[j] + dp[j - 1];}}return dp[n -1];}

这个题目包含了DP(动态规划)里的多个方面,比如重复子问题、记忆化搜索、滚动数组等等,这就是最简单的动态规划了,只不过我们这里的规划是dp[j] = dp[j] + dp[j -1] ;不用进行复杂的比较和计算。

3. 理解动态规划

DP一般是让我们找最值的,例如最长公共子序列,最关键的是DP问题的子问题不是相互独立的,如果递归直接分解会导致重复计算指数级增长,开头的热身题,而DP的最大价值是为了消除冗余,加速计算。

动态规划解决什么问题:A求有多少种走法,B输出所有的走法

动态规划计算效率高,但是不能找到满足要求的路径,

区分动态规划和递归最重要的一条是:动态规划只关心当前结果是什么,怎么来的就不管了,所以动态规划无法获得完整的路径,这与回溯不一样,回溯能够获得一条甚至所有满足要求的完整路径。

DP的基本思想是将待求解问题分解成若干个子问题,先求子问题,再从这些子问题中得到原问题的解,既然要找最值,那么必然要做的就是穷举来找所有的可能,然后选择“最”的那个,这就是为什么再DP代码中大量判断逻辑都会被套上min()或者max(),

既然穷举,那为什么还有DP的概念?这是因为穷举的过程中存在大量的重复计算,效率低下,所以我们要使用记忆化搜索等方式来消除不必要的计算,所谓记忆化搜索就是将已经计算好的结果先存在数组里面,后面就直接读就不再重复计算了,

既然记忆化能解决问题,为啥DP这么难,因为DP问题一定具备“最优子结构”,这样才能让记忆时得到准确结果,至于什么时最优子结构,后面还有具体问题,

有了最优子结构,还要正确的“状态转移方程”,才能正确的穷举,也就是递归关系,大部分递归都可以通过数组实现,因此代码结构一般是这样的for循环,这就是DP的基本模板:

//初始化base case ,也就是刚开始的几种场景,有几种枚举
        dp[0][0][...] = base case
//进行状态转移
        for 状态1 状态1的所有取值
                for 状态2 in 状态2的所有取值
                        dp[状态1][状态2] = 求最值Max(选择1,选择2,...)

动态规划题目有三种基本类型:

1. 计数有关,例如求多少种方式到右下角,有多少种方式选出K个数是使得什么什么的问题,不关心路径是什么

2. 求最大值最小值,最多最少等,例如最大数字和,最长上升子序列,最长公共子序列,最长回文序列等

3. 求存在性,例如取石子游戏,先手是否必胜,能不能选出k个数使得什么什么等等

不管那种解决问题的模板也是类似的

  • 第一步:确定状态和子问题,也就是枚举出某个位置所有的可能性,对于DP,大部分题目分析最后一步更容易一些,得到递推关系,同时将问题转换为子问题。
  • 第二步:确定状态转移方程,也就是数组要存储什么内容,很多时候状态确定之后,状态转移方程也就确定了,前两步也可作为为第一步骤
  • 第三步:确定初始和边界条件情况,注意细心,尽量周全
  • 第四步:按照从小到大的顺序计算:f[0],f[1],f[2]

我们自始至终,都要在大脑里装一个数组(可能是一维,也可能是二维),要看这个数组每个元素的含义是什么(也就是状态),要看每个数组是根据谁来算的(状态转移方程),然后就是从小到大挨着将数组填满(从小到大计算,实现记忆化搜索),最后看那个位置是我们想要的结果。

相关文章:

算法通关村 | 透彻理解动态规划

1. 斐波那契数列 1&#xff0c;1&#xff0c;2&#xff0c;3&#xff0c;5&#xff0c;8&#xff0c;13&#xff0c;..... f(n) f(n-1) f(n-2) 代码实现 public static int count_2 0;public int fibonacci(int n){if (n < 2){count_2;return n;}int f1 1;int f2 2;i…...

数据结构(持续更新)

嗯,怎么说数据结构果然很玄妙。按照能不能存储多行元素大致分为两类。 不能存好几行的数据包括pair,int,float,double,char,struct; 能存好几行的:map,unordered_map,list,vector,set,string,array。 1. pair “pair” 是 C++ 标准库中的一个模板类,它用于存储…...

nginx部署vue后显示500 Internal Server Error解决方案

前言 描述&#xff1a;当我配置好全部之后&#xff0c;通过 服务器 ip 地址访问&#xff0c;遇到报错信息&#xff1a;500 Internal Server Error。 今天部署vue前端项目一直报错500&#xff0c;无法显示出主页面。 一个以为是自己的dist位置没有访问正确或者nginx.conf的位…...

微调大型语言模型(一):为什么要微调(Why finetune)?

今天我们来学习Deeplearning.ai的在线课程 微调大型语言模型(一)的第一课&#xff1a;为什么要微调(Why finetune)。 我们知道像GPT-3.5这样的大型语言模型(LLM)它所学到的知识截止到2021年9月&#xff0c;那么如果我们向ChatGPT询问2022年以后发生的事情&#xff0c;它可能会…...

【GO】网络请求例子

post请求;multipart/form-data类型 // 构建请求参数requestData : map[string]interface{}{"gb": "","code": "","reMemberInfo": map[string]interface{}{"shi": "","…...

泡泡玛特海外布局动作不断,开启东南亚潮玩盛会

近日&#xff0c;泡泡玛特海外布局动作不断&#xff0c;9月8日至10日&#xff0c;泡泡玛特2023 PTS潮流玩具展&#xff08;下简称新加坡PTS&#xff09;在新加坡滨海湾金沙成功举办&#xff0c;现场人气爆棚&#xff0c;三天吸引了超过2万观众入场&#xff0c;这也是泡泡玛特首…...

uniappAndroid平台签名证书(.keystore)生成

一、安装JRE环境 https://www.oracle.com/java/technologies/downloads/#java8 记住下载默认安装地址。ps&#xff1a;我都默认安装地址C:\Program Files\Java\jdk-1.8 二、安装成功后配置环境变量 系统变量配置 AVA_HOME 放到环境变量去 %JAVA_HOME%\bin 三、生成签名证书…...

Gateway学习和源码解析

文章目录 什么是网关&#xff1f;搭建实验项目demo-servicegateway-service尝试简单上手 路由&#xff08;Route&#xff09;断言&#xff08;Predicate&#xff09;和断言工厂&#xff08;Predicate Factory&#xff09;gateway自带的断言工厂After&#xff08;请求必须在某个…...

移动机器人运动规划 --- 基于图搜索的Dijkstra算法

移动机器人运动规划 --- 基于图搜索的Dijkstra算法 Dijkstra 算法Dijkstra 算法 伪代码流程Dijkstra 算法步骤示例Dijkstra算法的优劣分析 Dijkstra 算法 Dijkstra 算法与BFS算法的区别就是 : 从容器中弹出接下来要访问的节点的规则不同 BFS 弹出: 层级最浅的原则&#xff0c…...

Mybatis SQL构建器

上一篇我们介绍了在Mybatis映射器中使用SelectProvider、InsertProvider、UpdateProvider、DeleteProvider进行对数据的增删改查操作&#xff1b;本篇我们介绍如何使用SQL构建器在Provider中优雅的构建SQL语句。 如果您对在Mybatis映射器中使用SelectProvider、InsertProvider…...

怎么将几张图片做成pdf合在一起

怎么将几张图片做成pdf合在一起&#xff1f;在我们平时的工作中&#xff0c;图片和pdf都是非常重要的电脑文件&#xff0c;使用也非常频繁&#xff0c;图片能够更为直观的展示内容&#xff0c;而pdf则更加的正规&#xff0c;很多重要文件大多会做成pdf格式的。在职场人的日常工…...

关于JPA +SpringBoot 遇到的一些问题及解决方法

关于JPA SpringBoot 遇到的一些问题及解决方法&#xff08;可能会有你正在遇到的&#xff09; 一、JpaRepository相关 1.1 org.springframework.dao.InvalidDataAccessResourceUsageException: Named parameter not bound : id; nested exception is org.hibernate.QueryEx…...

​全国馆藏《乡村振兴战略下传统村落文化旅游设计》许少辉八一著作——2023学生开学季辉少许

​全国馆藏《乡村振兴战略下传统村落文化旅游设计》许少辉八一著作——2023学生开学季辉少许...

linux升级glibc-2.28

1.准备工作 1.1升级gcc到gcc8 # 安装devtoolset-8-gcc yum install centos-release-scl yum install devtoolset-8 scl enable devtoolset-8 -- bash# 启用工具 source /opt/rh/devtoolset-8/enable # 安装GCC-8 yum install -y devtoolset-8-gcc devtoolset-8-gcc-c devtoolse…...

[Go疑难杂症]为什么nil不等于nil

现象 在日常开发中&#xff0c;可能一不小心就会掉进 Go 语言的某些陷阱里&#xff0c;而本文要介绍的 nil ≠ nil 问题&#xff0c;便是其中一个&#xff0c;初看起来会让人觉得很诡异&#xff0c;摸不着头脑。 先来看个例子&#xff1a; type CustomizedError struct {Err…...

C#60个常见的问题和答案

在本文中,我将帮助你准备好在下一次面试中解决这些与C# 编程语言相关的问题。同时,你可能想练习一些C# 项目。这 60 个基本的 C#面试问题和答案将帮助你了解该语言的技术概念。 目录 什么是 C#? 1.什么是类? 2.面向对象编程的主要概念是什么?...

11:STM32---spl通信

目录 一:SPL通信 1:简历 2:硬件电路 3:移动数据图 4:SPI时序基本单元 A : 开/ 终条件 B:SPI时序基本单元 A:模式0 B:模式1 C:模式2 D:模式3 C:SPl时序 A:发送指令 B: 指定地址写 C:指定地址读 二: W25Q64 1:简历 2: 硬件电路 3:W25Q64框图 4: Flash操作注意…...

kafka的 ack 应答机制

目录 一 ack 应答机制 二 ISR 集合 一 ack 应答机制 kafka 为用户提供了三种应答级别&#xff1a; all&#xff0c;leader&#xff0c;0 acks &#xff1a;0 这一操作提供了一个最低的延迟&#xff0c;partition的leader接收到消息还没有写入磁盘就已经返回ack&#x…...

Django系列:Django开发环境配置与第一个Django项目

Django系列 Django开发环境配置与第一个Django项目 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article/details/1328…...

iPad协议/微信协议最新版

一、了解微信的协议 在开发微信协议之前&#xff0c;需要先了解微信的协议。微信的协议包括登录协议、消息传输协议、文件传输协议、数据同步协议等。其中&#xff0c;登录协议是最重要的协议之一&#xff0c;包括登录验证、登录认证等。消息传输协议则是微信最核心的功能之一…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...