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

算法训练营Day38(动态规划1)

 动态规划理论基础 

动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的

区别

动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的

例子

动态规划中dp[j]是由dp[j-weight[i]]推导出来的,然后取max(dp[j], dp[j - weight[i]] + value[i]),而贪心呢,每次拿物品选一个最大的或者最小的就完事了,和上一个状态没有关系,所以贪心解决不了动态规划的问题

 知道动规是由前一个状态推导出来的,而贪心是局部直接选最优的,对于刷题来说就够用了

动规五部曲

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

509. 斐波那契数 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

提醒

很简单的动规入门题,但简单题使用来掌握方法论的,用动规五部曲来分析。

一、动态规划

class Solution:def fib(self, n: int) -> int:# 排除 Corner Caseif n == 0:return 0# 创建 dp table dp = [0] * (n + 1)# 初始化 dp 数组dp[0] = 0dp[1] = 1# 遍历顺序: 由前向后。因为后面要用到前面的状态for i in range(2, n + 1):# 确定递归公式/状态转移公式dp[i] = dp[i - 1] + dp[i - 2]# 返回答案return dp[n]

二、递归

class Solution:def fib(self, n: int) -> int:if n < 2:return nreturn self.fib(n - 1) + self.fib(n - 2)

70. 爬楼梯   力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

提醒

本题先自己想一想, 之后会发现和 斐波那契数 有点关系。

class Solution:def climbStairs(self, n: int) -> int:if n <= 1:return ndp = [0] * (n + 1)dp[1] = 1dp[2] = 2for i in range(3, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]

思考

这道题目还可以继续深化,就是一步一个台阶,两个台阶,三个台阶,直到 m个台阶,有多少种方法爬到n阶楼顶。

这又有难度了,这其实是一个完全背包问题,但力扣上没有这种题目,大家可以去卡码网去做一下 57. 爬楼梯

746. 使用最小花费爬楼梯 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

提醒

明确说 第一步是不用花费的

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:dp = [0] * (len(cost) + 1)dp[0] = 0  # 初始值,表示从起点开始不需要花费体力dp[1] = 0  # 初始值,表示经过第一步不需要花费体力for i in range(2, len(cost) + 1):# 在第i步,可以选择从前一步(i-1)花费体力到达当前步,或者从前两步(i-2)花费体力到达当前步# 选择其中花费体力较小的路径,加上当前步的花费,更新dp数组dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])return dp[len(cost)]  # 返回到达楼顶的最小花费

相关文章:

算法训练营Day38(动态规划1)

动态规划理论基础 动态规划&#xff0c;英文&#xff1a;Dynamic Programming&#xff0c;简称DP&#xff0c;如果某一问题有很多重叠子问题&#xff0c;使用动态规划是最有效的。 区别 动态规划中每一个状态一定是由上一个状态推导出来的&#xff0c;这一点就区分于贪心&…...

基于Harris角点的多视角图像全景拼接算法matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 4.1 Harris角点检测 4.2 图像配准 4.3 图像变换和拼接 4.4 全景图像优化 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022a 3.部分核心程序 function [ImageB…...

数学建模--PageRank算法的Python实现

文章目录 1. P a g e R a n k PageRank PageRank算法背景2. P a g e R a n k PageRank PageRank算法基础2.1. P a g e R a n k PageRank PageRank问题描述2.2.有向图模型2.3.随机游走模型 3. P a g e R a n k PageRank PageRank算法定义3.1. P a g e R a n k PageRank PageRank…...

samba服务搭建,并将共享目录映射到windows

系统版本&#xff1a;centos7 1、centos 安装samba yum -y install samba 2、查看安装信息 rpm -qa |grep samba 3、设置开机自启动 systemctl enable smb.service systemctl enable nmb.service 4、设置samba服务器配置文件 sudo vi /etc/samba/smb.conf 注意&#…...

golang 中使用 statik 将静态资源编译进二进制文件中

现在的很多程序都会提供一个 Dashboard 类似的页面用于查看程序状态并进行一些管理的功能&#xff0c;通常都不会很复杂&#xff0c;但是其中用到的图片和网页的一些静态资源&#xff0c;如果需要用户额外存放在一个目录&#xff0c;也不是很方便&#xff0c;如果能打包进程序发…...

北京住总集团携手云轴科技ZStack获行业云平台领航者创新实践奖

为进一步促进行业企业上云、用数、赋智发展&#xff0c;落实国家政策&#xff0c;加速云计算应用从互联网拓展至政务、金融、交通、电信等行业&#xff0c;推动以云计算为核心的数字产业创新&#xff0c;1月18日中国信息通信研究院主办的“企业上云用云专项行动会—行业云平台研…...

【漏洞攻击之文件上传条件竞争】

漏洞攻击之文件上传条件竞争 wzsc_文件上传漏洞现象与分析思路编写攻击脚本和重放措施中国蚁剑拿flag wzsc_文件上传 漏洞现象与分析 只有一个upload前端标签元素&#xff0c;并且上传任意文件都会跳转到upload.php页面&#xff0c;判定是一个apache容器&#xff0c;开始扫描…...

Buttton样式设置background属性失效的问题

最近遇到一个之前没有遇见的问题&#xff0c;就是在添加Button控件的时候发现对其设置background时没有效果&#xff0c;原因是AndroidStudio升级后默认按钮就是主题色&#xff0c;一个比较简单的方法是将Button改为android.widget.Button&#xff0c;对比效果如下&#xff1a;…...

使用vue-pdf插件加载pdf

安装&#xff1a; // 安装这个版本&#xff0c;其它版本会有千奇百怪的错&#xff0c;这个版本和4.0.0都是可以的 cnpm install vue-pdf4.2.0// 安装pdfjs-dist cnpm install pdfjs-dist2.5.207 使用&#xff1a; // 我的css样式是pxToRem&#xff0c;友友们使用可能样式会有…...

BP蓝图映射到C++笔记1

教程链接&#xff1a;示例1&#xff1a;CompleteQuest - 将蓝图转换为C (epicgames.com) 1.常用的引用需要记住&#xff0c;如图所示。 2.蓝图中可以调用C函数&#xff0c;也可以实现C函数 BlueprintImplementableEvent:C只创建&#xff0c;不实现&#xff0c;在蓝图中实现 B…...

龙芯+RT-Thread+LVGL实战笔记(30)——电子琴演奏

【写在前面】正值期末,笔者工作繁忙,因此本系列教程的更新频率有所放缓,还望订阅本专栏的朋友理解,请勿催更。笔者在此也简要声明几点: 有些硬件模块笔者并没有,如LED点阵、压力传感模块、RFID模块等,因此这些模块的相关任务暂时无法给出经过验证的代码。其实,教程进行…...

Python Process创建进程(2种方法)详解

虽然使用 os.fork() 方法可以启动多个进程&#xff0c;但这种方式显然不适合 Windows&#xff0c;而 Python 是跨平台的语言&#xff0c;所以 Python 绝不能仅仅局限于 Windows 系统&#xff0c;因此 Python 也提供了其他方式在 Windows 下创建新进程。 Python 在 multiproces…...

树莓派4B 使用树莓派官方烧录器烧录ubuntu20.04.5 排坑

问题描述&#xff1a; 使用树莓派官方烧录器烧录ubuntu并且在烧录器中设置了电脑热点&#xff0c;但是无法连接WIFI。重启后也无效。 排坑&#xff1a; 1.首先打开/boot中的network-config&#xff0c;发现烧录器设置的密码是乱码&#xff0c;重新设置&#xff1b; 2.有博主说…...

鸿蒙开发(五)鸿蒙UI开发概览

从用户角度来讲&#xff0c;一个软件拥有好看的UI&#xff0c;那是锦上添花的事情。再精确的算法&#xff0c;再厉害的策略&#xff0c;最终都得通过UI展现给用户并且跟用户交互。那么&#xff0c;本篇一起学习下鸿蒙开发UI基础知识&#xff0c;认识下各种基本控件以及使用方式…...

应用层—HTTP详解(抓包工具、报文格式、构造http等……)

文章目录 HTTP1. 抓包工具的使用1.1 配置信息1.2 观察数据 2. 分析 https 抓包结果3. HTTP请求详解3.1 认识 URL3.1.1 URL 基本格式3.1.2 查询字符串 (query string)3.1.3 关于 URL Encode 3.2 认识 http 方法3.2.1 [经典问题] Get 和 Post 主要的区别是什么&#xff1f;&#…...

ISA Server 2006部署网站对比nginx

2024年了&#xff0c;我还是第1次使用ISA Server 。没办法在维护一个非常古老的项目。说到ISA Server可能有小伙们不清楚&#xff0c;但是说到nginx大家应该都知道吧。虽然他们俩定位并不相同&#xff0c;但是本文中提到的需求&#xff0c;他俩是都可以实现。 网上找的到的教程…...

CHAPTER 9: 《DESIGN A WEB CRAWLER》第9章 《设计一个web爬虫》

CHAPTER 9: 《DESIGN A WEB CRAWLER》第九章 设计一个web爬虫 在本章中&#xff0c;我们将重点介绍网络爬虫设计&#xff1a;一种有趣而经典的系统设计 面试问题。 网络爬虫被称为机器人或蜘蛛。它被搜索引擎广泛用于发现网络上的新内容或更新内容。内容可以是网页、图像、视频…...

java SSM网上小卖部管理系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

一、源码特点 java SSM网上小卖部管理系统是一套完善的web设计系统&#xff08;系统采用SSM框架进行设计开发&#xff0c;springspringMVCmybatis&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源 代码和数据库&#xff0c;系统主要…...

Java中集合元素的删除

关于集合元素的remove 重点&#xff1a;当集合的结构发生改变时&#xff0c;迭代器必须重新获取&#xff0c;如果还是用以前老的迭代器&#xff0c;会出现异常 java.util.ConcurrentModificationException 重点&#xff1a;在迭代集合元素的过程中&#xff0c;不能调用集合对象…...

HNU-数据挖掘-实验2-数据降维与可视化

数据挖掘课程实验实验2 数据降维与可视化 计科210X 甘晴void 202108010XXX 文章目录 数据挖掘课程实验<br>实验2 数据降维与可视化实验背景实验目标实验数据集说明实验参考步骤实验过程1.对数据进行初步降维2.使用无监督数据降维方法&#xff0c;比如PCA&#xff0c;I…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...