动态规划的解题思想

1. 从斐波那契数列说起

斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 01 开始, ,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0, F(2) = 1

F(n) = F(n - 1) + F(n - 2),其中 n >= 2

给定 n ,请计算 F(n)

当我们看完上述问题后,心中一阵窃喜:答案不就在题目当中吗。

于是马上就写出了如下代码:

#暴力递归
def fib(n):if n == 0 or n == 1:return nreturn fib(n - 1) + fib(n - 2)

不幸的是,当我们提交完代码后,大概率会收到 leetcode 的超时警告!why,接下来我们分析一下上述代码的执行情况。假设 n=5 时,具体的执行逻辑如下图所示:

我们不难发现 fib(3) 计算了两次。如果这个差距不够明显的话,我们可以假设 n=10,再去画执行逻辑图,就会发现需要重复计算的情况成指数级增长,这就是耗时的主要原因。

然后我们想出了一种空间换时间的方法,把每次 fib 函数计算的结果缓存到一个哈希表中,下次再遇到相同的数则无需计算,直接查表即可,这样就大大减少了运算量。

#备忘录递归
map = {}
def fib(n):if n == 0 or n == 1:return nelif n in map:return map[n]map[n] = fib(n - 1) + fib(n - 2)return map[n]

2. 何为动态规划

上述解法通常被命名为备忘录递归解法,事实上备忘录递归法和动态规划只是在实现上稍有不同,其核心思想和目标完全一致,拆分子问题,记住过往,减少重复计算,甚至个人认为备忘录递归就是广义上的动态规划。

动态规划就是将一个问题拆分为若干的子问题,直到子问题被解决,保存子问题结果,然后递推出原问题的答案。

同样是上面的例子,我们既然知道 1 和 2 的值,就能推算出 3,4....n 的值。

我们不妨来定义一个数组 nums,nums[i] 表示斐波那契的第 i 项,递推的给数组赋值,返回第 n 项即为所求结果。不过为了强调动态规划,我们通常会将这个数组命名为 dp(Dynamic Programming)。

#动态规划解法
def fib(n):if n < 2:return ndp = [0] * (n + 1)dp[0] = 0dp[1] = 1for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]

3. 何时&如何使用动态规划

通过上述的例子,相信大家已经对动态规划有了一些认识,那么什么情况下我们可以使用动态规划呢?

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

如何使用动态规划的思想解题呢?

  1. 找到相同问题(也叫重叠子问题),这个相同问题必须能适配不同规模

  2. 找到相同问题 不同规模之间的关系(这个关系叫状态转移方程)

  3. 找到问题的特殊解,然后递推出所有规模的解

(简单的理解就是:定义 dp 表格的含义,找出后边数据和前边数据的关系,然后依次填表,直到找出最终解)

本节比较抽象,大家可以看完下一节的经典题目后再回来理解。

4. 经典题目

还是回到上面的例子,我们之所以能很容易写出上面代码,是因为题目中已经把状态转移方程直接写到了题目中。而大部分情况这个方程并非那么明显,需要我们去分析,这也是动态规划的难点所在。

下面的几个经典题目,我们只分析出状态转移方程,不实现具体代码,目的是体会理解动态规划的套路。

4.1 打家劫舍

一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 1:

输入:[1,2,3,1] 输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

第一步找到重叠子问题,要适配所有的规模。因为这是一个一位数组所有使用 dp[i] 就能表示所有的规模,那么 dp[i]表示什么含义呢?表示小偷从 0-i 范围内可以偷窃的最高金额。

第二步列状态转移方程。分析下图前 i 项的最大值,包含两个情况,要么包含第 i 项要么不包含第 i 项。

如果不包含第 i 项, 则 dp[i] = dp[i-1]

如果包含第 i 项,由于相邻的房屋不能偷窃,则一定不能包含第 i-1 项,所以 dp[i] = dp[i-2] + 数组的第 i 项的值

由于求的是最优的结果 所以 dp[i] 应该是以上两种情况中值较大的情况。

列出方程 dp[i] = max(dp[i-1], dp[i-2]+nums[i])

第三步确定特殊解,当房屋数等于 1 时,最优解就是只偷一间;当房屋数等于 2 时,最优解就是偷价值较大的一间。

接下来递推填表,返回最终解。

4.2 不同路径

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

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

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

首先第一步,我们要找到重叠子问题,这些子问题要能适配所有的规模。这里有行也有列,所以我们需要两个参数来表示这个子问题 dp[i][j],表示的含义就是从开始走到第 i 行第 j 列的所有路径数。

第二步,确定状态转移方程。观察下图,我们会发现 dp[i][j]的路径数只和两个格子有关 dp[i][j-1]和 dp[i-1][j],且是他们两个的和,所以状态转移方程应该是 dp[i][j] = dp[i][j-1] + dp[i-1][j]

第三步,确定特殊解,第 1 行和第 1 列所有的数据都只有一种情况,要么一直向右走要么一直向下走,所以全部赋值为 1,然后递推填表,直到返回最终结果。

4.3 01 背包

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i],得到的价值是 value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。

示例 1:

物品重量为:[1,3,4]

物品价值为:[15,20,30]

背包能背的最大重量为:4

输出最大价值:35

解释:背包可以放入 0 和 1 号商品,价值为 15+20=35,也可以只放 2 号商品,价值为 30。

第一步找重叠子问题,确定 dp 表含义

按照前面的经验我们通常会将 dp[i]定义为 从 0 到 i 最优的情况,干脆我们也将 dp[i] 定义为 从 0 到 i 件商品中可选的最大价值。然而我们继续往下分析时,并没有找到不同规模问题之间的联系。

另一方面我们还可以从背包容量上拆分子问题,比如如果知道背包容量为 3 时的最大价值,是否可以推导出容量为 4 时的最大价值,经过一番思考计算,好像也找不到不同规模之间的联系。

此时聪明的你,一定能想到,要不然将以上两个纬度同时进行拆分找一下其中的规律。那么我们就会得到下面一个二维 dp 表。其中 dp[i][j] 表示从 0-i 中选择的物品放入容量为 j 的背包中的最大价值

第二步分析不同规模问题之间的联系,列出状态转移方程

此时有两种情况,i 物品选还是不选。此时状态表达式有了一个基本的雏形:

dp[i][j] = max(选第 i 件商品,不选第 i 件商品)。

首先看不选的情况,这种情况比较简单,如果不选那么最大价值就等于同等容积背包内,前面商品所能凑出的最大价值。直接写出表达式 dp[i][j] = dp[i-1][j]

接下来分析选的情况,如果选择了第 i 个商品 那么此时的最大价值应该是 商品i本身的价值 + 商品i-1范围内 且 背包容量为(j-商品i的重量)的最大价值,写成表达式为dp[i][j] = value[i] + dp[i-1][j-weight[i]]

综上最终的表达式为 dp[i][j] = max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]]),另外还需要处理一些边界条件,例如当商品本身重量大于背包容量时等。此处就不展开描述了。

第三步找出特殊解

当物品下表为 0 时,之前看当前商品是否可以放入背包内,可以放入最大价值就是当前商品价值,否则最大价值就是 0,然后递推填表。

学到这里,恭喜你,你已经拿到了 leetcode 刷动态规划类题目的入场券!

5. 空间复杂度的优化

最后我们再来聊一下空间复杂度的优化。

上面我们说过,动态规划的核心就是记住过往,减少重复计算, 牺牲空间去换取时间,那么我们到底牺牲了多少空间?

回到斐波那契数列,我们定义了一个长度为 n 的数组来缓存过程中的计算结果,所以空间复杂度为 O(n),然后仔细观察我们就会发现,当我们计算 dp[i] 时,并不需要整个数组,而是只需两个数字。所以我们只需定义两个数据,每次记得更新数据即可。这样就可以将空间复杂度降低到常量级 O(1)。

接下来我们看不同路径的题目,在这里我们定义了一个二位数组,所以空间复杂度为 O(m*n);继续观察我们发现 dp[i][j] 只和当前行和上一行的数据关联。那我们就可以这样做,定义一个一维数组,先把数组全部填充 1(相当于二维数组的第一行),之后的行从左往右覆盖当前的一维数组,假设覆盖到了第 i-1 位,此时一位数组的含义,i 左边的数据表示的是当前行的数据,i 及右边的数据表示上一行的数据。原本的状态转移方程dp[i][j] = dp[i][j-1] + dp[i-1][j]就可以优化成 dp[i] = dp[i-1]+dp[i],空间复杂度也降到了 O(n)

这里总结出来,很多动态规划问题可以通过“空间降维”只缓存当前被需要的数据,来降低空间复杂度。

6. 团队介绍

三翼鸟数字化技术平台-场景设计交互平台」主要负责设计工具的研发,包括营销设计工具、家电VR设计和展示、水电暖通前置设计能力,研发并沉淀素材库,构建家居家装素材库,集成户型库、全品类产品库、设计方案库、生产工艺模型,打造基于户型和风格的AI设计能力,快速生成算量和报价;同时研发了门店设计师中心和项目中心,包括设计师管理能力和项目经理管理能力。实现了场景全生命周期管理,同时为水,空气,厨房等产业提供商机管理工具,从而实现了以场景贯穿的B端C端全流程系统。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/422872.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

机器学习--卷积神经网络(包括python实现)

卷积神经网络 1. 计算方法 &#xff08;1&#xff09;输入和输出channel 1时 首先我们要知道channel是什么意思&#xff0c;顾名思义channel就是“通道”的意思qwq。我们来举个例子&#xff0c;在计算机视觉中&#xff0c;如果一张图片是黑白的&#xff0c;那么每个像素点都…

Linux中使用Docker构建Nginx容器完整教程

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f427;Linux基础知识(初学)&#xff1a;点击&#xff01; &#x1f427;Linux高级管理防护和群集专栏&#xff1a;点击&#xff01; &#x1f510;Linux中firewalld防火墙&#xff1a;点击&#xff01; ⏰️创作…

JD18年秋招笔试疯狂数列python解答

问题如下&#xff1a; 链接&#xff1a;疯狂序列_京东笔试题_牛客网 [编程题]疯狂序列 热度指数&#xff1a;149 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 32M&#xff0c;其他语言64M 东东从京京那里了解到有一个无限长的数字序列: 1…

uniapp 做一个查看图片的组件,图片可缩放移动

因为是手机端&#xff0c;所以需要触摸可移动&#xff0c;双指放大缩小。 首先在components里建个组件 查看图片使用 uni-popup 弹窗 要注意 transform的translate和scale属性在同一标签上不会一起生效 移动就根据触摸效果进行偏移图片 缩放就根据双指距离的变大变小进行缩…

DFS算法专题(二)——穷举vs暴搜vs深搜vs回溯vs剪枝【OF决策树】

目录 1、决策树 2、算法实战应用【leetcode】 2.1 题一&#xff1a;全排列 2.2.1 算法原理 2.2.2 算法代码 2.2 题二&#xff1a;子集 2.2.1 算法原理【策略一】 2.2.2 算法代码【策略一】 2.2.3 算法原理【策略二&#xff0c;推荐】 2.2.4 算法代码【策略二&#x…

浅谈基于负荷时空均衡和弹性响应的电动汽车快充电价定价策略

摘要&#xff1a;为了引导电动汽车有序充电&#xff0c;提出了一种考虑负荷时空均衡和弹性响应的电动汽车快充电价定价策略。引入交通流理论描述交通路网&#xff0c;建立电动汽车快充负荷时空分布模型&#xff1b;考虑配电网调度和电动汽车快充负荷的弹性需求&#xff0c;构建…

React Native 0.76,New Architecture 将成为默认模式,全新的 RN 来了

关于 React Native 的 New Architecture 概念&#xff0c;最早应该是从 2018 年 RN 团队决定重写大量底层实现开始&#xff0c;因为那时候 React Native 面临各种结构问题和性能瓶颈&#xff0c;最终迫使 RN 团队开始进行重构。 而从 React Native 0.68 开始&#xff0c;New A…

轻松搞定Arduino开发环境,像玩积木一样简单!

朋友们,有没有人和我一样,曾经对Arduino望而却步?说到“开发环境”这几个字,感觉脑子就要爆炸了,光是想象安装各种软件、调试环境就能把人吓跑。相信我,我也曾有过这样的感觉。但是,当我真正开始玩Arduino后,我发现一切都不像想象中那么复杂!其实,搭建Arduino开发环境…

光耦合器的工作原理和故障诊断

光耦合器&#xff0c;也称为光隔离器&#xff0c;是现代电子设备中必不可少的组件&#xff0c;尤其是在确保系统不同部分之间的电气隔离方面。它们通过使用光传输信号来防止高压或不需要的信号影响敏感组件。在本文中&#xff0c;我们将讨论光耦合器的工作原理、故障诊断和识别…

安泰功率放大器有哪些特点呢

功率放大器是电子设备中的重要组成部分&#xff0c;其作用是将输入信号的电功率放大到足够的水平&#xff0c;以驱动负载&#xff0c;如扬声器或天线。功率放大器有一些独特的特点&#xff0c;这些特点对于各种应用至关重要。下面将详细介绍功率放大器的特点&#xff0c;以更好…

Unity教程(十五)敌人战斗状态的实现

Unity开发2D类银河恶魔城游戏学习笔记 Unity教程&#xff08;零&#xff09;Unity和VS的使用相关内容 Unity教程&#xff08;一&#xff09;开始学习状态机 Unity教程&#xff08;二&#xff09;角色移动的实现 Unity教程&#xff08;三&#xff09;角色跳跃的实现 Unity教程&…

前端JS必用工具【js-tool-big-box】学习,获取全球热点城市当前时间、时区以及令时

js-tool-big-box工具库&#xff0c;之前也添加了几个热点城市的当前时间显示&#xff0c;但当时城市较少&#xff0c;功能也比较简单&#xff0c;只是显示了时分秒。 最近有使用者说&#xff0c;光有时分秒&#xff0c;功能太少&#xff0c;所以对js-tool-big-box工具库做了改进…

windows vscode ssh 连接远程服务器

1.在 PowerShell 中运行以下命令&#xff0c;查看 OpenSSH 客户端是否已安装 Get-WindowsCapability -Online | Where-Object Name -like OpenSSH.Client*如果有安装的话&#xff0c;如下图 2.如果没有安装&#xff0c;那么用下面的命令进行安装 Get-WindowsCapability -On…

科研绘图系列:R语言宏基因组PCoA图(PCoA plot)

介绍 PCoA(主坐标分析,也称为主轴分析)是一种多维统计技术,用于分析和可视化高维数据集,如宏基因组数据。在宏基因组学中,PCoA图用于展示样本之间的相似性和差异性,通常基于样本之间的距离或相似度矩阵。PCoA图说明: 样本间关系:PCoA图通过降维技术将高维数据投影到二…

(不用互三)AI绘画工具大比拼:Midjourney VS Stable Diffusion该如何选择?

文章目录 &#x1f4af;如何选择合适的AI绘画工具根据个人需求选择1. 您喜欢什么风格的绘画&#xff1f;2. 您想要创作什么主题的内容&#xff1f;3. 您对绘画工具的使用经验如何&#xff1f; 比较工具特点1. 工具的易用性和功能性如何&#xff1f;易用性&#xff1a;功能性&am…

【机器学习】分类与回归——掌握两大核心算法的区别与应用

【机器学习】分类与回归——掌握两大核心算法的区别与应用 1. 引言 在机器学习中&#xff0c;分类和回归是两大核心算法。它们广泛应用于不同类型的预测问题。分类用于离散的输出&#xff0c;如预测图像中的对象类型&#xff0c;而回归则用于连续输出&#xff0c;如预测房价。…

Linux | 进程控制(上):进程终止(strerror函数、errno宏、_exit() 与 exit())

文章目录 进程控制1、进程终止1.1进程常见退出方法退出码1.1.1 strerror函数 & errno宏1.1.1 _exit函数_exit和exit的区别结合现象分析&#xff1a; 进程控制 1、进程终止 1.1进程常见退出方法 进程退出场景 代码运行完毕&#xff0c;结果正确代码运行完毕&#xff0c;结…

Redis 集群高可用详解及配置

关型数据库 关系型数据库&#xff1a; 是建立在关系模型基础上的数据库&#xff0c;其借助于集合代数等数学概念和方法来处理数据库中的数据 主流的 MySQL、Oracle、MS SQL Server 和 DB2 都属于这类传统数据库 关型数据库的优缺点 特点&#xff1a; 1、数据关系模型基于关系…

学生请假管理系统

&#x1f449;文末查看项目功能视频演示获取源码sql脚本视频导入教程视频 1 、功能描述 学生请假管理系统拥有两种角色 管理员&#xff1a;班级管理、课程管理、学生管理、审核请假信息、导出请假单 学生&#xff1a;填写请假单、查看请假审核情况 1.1 背景描述 学生请假管…

音视频入门基础:WAV专题(11)——FFmpeg源码中计算WAV音频文件每个packet的pts_time、dts_time的实现

音视频入门基础&#xff1a;WAV专题系列文章&#xff1a; 音视频入门基础&#xff1a;WAV专题&#xff08;1&#xff09;——使用FFmpeg命令生成WAV音频文件 音视频入门基础&#xff1a;WAV专题&#xff08;2&#xff09;——WAV格式简介 音视频入门基础&#xff1a;WAV专题…