[代码随想录Day32打卡] 理论基础 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯
理论基础
题型
- 动归基础(这一节就是基础题)
- 背包问题
- 打家劫舍
- 股票问题
- 子序列问题
动态规划五部曲
- 确定dp数组及其下标的含义
- 确定递推公式
- dp数组如何初始化
- 遍历顺序
- 打印dp数组
509. 斐波那契数
简单~
- dp数组及下标含义: dp[i]表示第i各斐波那契数,值为dp[i]
- 递推公式:dp[i] = dp[i-1] -dp[i-2]
- dp数组如何初始化:dp[0] = 0; dp[1] = 1;题目描述中有敌意
- 遍历顺序:从前往后
- 打印dp数组
当前位置的值只与该位置的前两个数值有关,只需要维护长度为2的数组。
class Solution {
public:int fib(int n) {if(n==0 || n==1) return n;vector<int> dp(2);dp[0] = 0; dp[1] = 1;for(int i=2; i<=n; i++){int sum = dp[1] + dp[0];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};
class Solution {public int fib(int n) {if(n == 0 || n == 1) return n;int[] dp = new int[2];dp[0] = 0; dp[1] = 1;for(int i = 2; i<=n; i++){int sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
}
class Solution(object):def fib(self, n):""":type n: int:rtype: int"""if n == 0 or n == 1:return ndp = [0,1]for i in range(2, n+1):sum_ = dp[0] + dp[1]dp[0] = dp[1]dp[1] = sum_return dp[1]
参考文章
- https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
70. 爬楼梯
要明白如果爬n层有两种情况: 一种是从n-2层迈两步上来的,一种是从n-1层迈一步上来的。所以到达第n层的方法数量=到达第n-2层的方法数+到达第n-1层的方法数。
- dp数组及其下标含义 dp[i] 表示到达第i层的方法数量
- 递推公式 dp[i] = dp[i-1] + dp[i-2]
- dp数组初始化 dp[1] = 1 dp[2] = 2,0没有实际意义
- 遍历顺序:从前往后
- 打印dp数组
当前位置数值只与当前位置前2个位置数值有关,只需要维护长度为2的数组,但是0没有实际意义,为了实现更加明确的初始化我们定义长度为3的数组,0这个位置不进行初始化。
class Solution {
public:int climbStairs(int n) {if(n==1 || n==2) return n;vector<int> dp(3);dp[1] = 1;//空出0来因为没有意义dp[2] = 2;for(int i = 3; i <= n; i++){int sum = dp[1] + dp[2];dp[1] = dp[2];dp[2] = sum;}return dp[2];}
};
class Solution {public int climbStairs(int n) {if(n == 1 || n == 2) return n;int[] dp = new int[3];dp[1] = 1; dp[2] = 2;for(int i = 3; i <= n; i++){int sum = dp[1] + dp[2];dp[1] = dp[2];dp[2] = sum;}return dp[2];}
}
class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n == 1 or n == 2:return ndp = [None, 1, 2]for i in range(3, n+1):sum_ = dp[1] + dp[2]dp[1] = dp[2]dp[2] = sum_return dp[2]
参考文章
- https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
746. 使用最小花费爬楼梯
Note:注意题目描述,该位置不花费体力,往上跳花费体力。并且cost的长度是顶楼。
- dp数组及其下标含义:dp[i] 到达第i层所需要的最小花费为dp[i]
- 递推公式: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
- dp数组如何初始化: dp[0]=0;dp[1]=0;//因为当前位置不花费,向上跳才花费所以都初始化为0
- 遍历顺序:从前往后
- 打印dp数组
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {if(cost.size()<2) return 0;vector<int> dp(2);for(int i = 2; i <= cost.size(); i++){int minCost = min(dp[0] + cost[i-2], dp[1] + cost[i-1]);dp[0] = dp[1];dp[1] = minCost;}return dp[1];}
};
class Solution {public int minCostClimbingStairs(int[] cost) {if(cost.length<2) return 0;int[] dp = new int[]{0, 0};for(int i = 2; i <= cost.length; i++){int minCost = Math.min(dp[0] + cost[i-2], dp[1] + cost[i-1]);dp[0] = dp[1];dp[1] = minCost;}return dp[1];}
}
class Solution(object):def minCostClimbingStairs(self, cost):""":type cost: List[int]:rtype: int"""if len(cost)<2:return 0dp = [0, 0]for i in range(2, len(cost)+1):minCost = min(dp[0]+cost[i-2], dp[1]+cost[i-1])dp[0] = dp[1]dp[1] = minCostreturn dp[1]
参考文章
- https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html
相关文章:
[代码随想录Day32打卡] 理论基础 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯
理论基础 题型 动归基础(这一节就是基础题)背包问题打家劫舍股票问题子序列问题 动态规划五部曲 确定dp数组及其下标的含义确定递推公式dp数组如何初始化遍历顺序打印dp数组 509. 斐波那契数 简单~ dp数组及下标含义: dp[i]表示第i各斐…...
android NumberPicker隐藏分割线或修改颜色
在 Android 中,可以通过以下几种方法隐藏 NumberPicker 的分割线: 使用 XML 属性设置 在布局文件中的 NumberPicker 标签内添加 android:selectionDividerHeight"0dp" 属性,将分割线的高度设置为 0,从而达到隐藏分割线…...
7-2 二分查找
输入n值(1<n<1000)、n个非降序排列的整数以及要查找的数x,使用二分查找算法查找x,输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。 输入格式: 输入共三行: 第一行是n值࿱…...
mid360使用cartorapher进行3d建图导航
1. 添加urdf配置文件: 添加IMU配置关节点和laser关节点 <!-- imu livox --> <joint name"livox_frame_joint" type"fixed"> <parent link"base_link" /> <child link"livox_frame" /> <o…...
Ubuntu安装grafana
需求背景:管理服务器,并在线预警,通知 需求目的: 及时获取服务器状态 技能要求: 1、ubuntu 2、grafana 3、prometheus 4、node 步骤: 一、grafana安装 1、准备系统环境,配置号网络 2、…...
Java版-图论-最短路-Floyd算法
实现描述 网络延迟时间示例 根据上面提示,可以计算出,最大有100个点,最大耗时为100*wi,即最大的耗时为10000,任何耗时计算出来超过这个值可以理解为不可达了;从而得出实现代码里面的: int maxTime 10005…...
可视化建模以及UML期末复习篇----UML图
这是一篇相对较长的文章,如你们所见,比较详细,全长两万字。我不建议你们一次性看完,直接跳目录找你需要的知识点即可。 --------欢迎各位来到我UML国! 一、UML图 总共有如下几种: 用例图(Use Ca…...
HTML常见标签列表,涵盖了多种用途的标签。
文档结构标签 <!DOCTYPE html>:声明文档类型,告诉浏览器使用HTML5标准。<html>:HTML文档的根元素。<head>:包含文档的元数据(meta-data),如标题、字符集、样式表链接、脚本等…...
FPGA 16 ,Verilog中的位宽:深入理解与应用
目录 前言 一. 位宽的基本概念 二. 位宽的定义方法 1. 使用向量变量定义位宽 ① 向量类型及位宽指定 ② 位宽范围及位索引含义 ③ 存储数据与字节数据 2. 使用常量参数定义位宽 3. 使用宏定义位宽 4. 使用[:][-:]操作符定义位宽 1. 详细解释 : 操作符 -: 操作符 …...
vue-生命周期
Vue 的生命周期是指 Vue 实例从创建到销毁期间经历的一系列阶段。每个阶段都有相应的钩子函数(Lifecycle Hooks),允许开发者在这些关键时刻执行自定义逻辑。 一、钩子函数 1. 创建阶段 beforeCreate 在实例初始化之后,数据观测 …...
浅谈Kubernetes(K8s)之RC控制器与RS控制器
1.RC控制器 1.1RC概述 Replication Controller 控制器会持续监控正在运行的Pod列表,并保证相应类型的Pod的数量与期望相符合,如果Pod数量过少,它会根据Pod模板创建新的副本,反之则会删除多余副本。通过RC可实现了应用服务的高可用…...
本题要求采用选择法排序,将给定的n个整数从大到小排序后输出。
#include <stdio.h> #define MAXN 10 int main() { int i, index, k, n, temp; int a[MAXN]; scanf("%d", &n); for (i 0; i < n; i) { scanf("%d", &a[i]); } // 外层循环控制排序轮数,一共需要n-1轮 for (k 0; k < n…...
Linux: glibc: 频繁调用new/delete会不会导致内存的碎片
最近同事问了一个问题:频繁调用new/delete会不会导致内存的碎片。 下面是我想到的一些回答, glibc的内存处理机制,是在释放的时候会自动将小块内存整合成大块内存,为接下来满足大块的需求的可能。而且程序也不是一直占着内存不释放(如果是一直不释放,要考虑是不是内存泄漏…...
量子变分算法---损失函数
引子 关于损失函数,我们知道在强化学习中,会有一个函数,用来表示模型每一次行为的分数,通过最大化得分,建立一个正反馈机制,若模型为最优则加分最多,若决策不佳则加很少分或者扣分。而在神经网络…...
计算机的性能评估
目录 计算机的性能评估 确定性能指标 考虑通讯因素 考虑机器过热因素 综合评估模型 动态评估与调整 计算机的性能评估 在分布式计算机系统中,综合考虑各种因素来评估性能是一个复杂但重要的问题。以下是一种可能的方法来综合考虑评估分布式计算机性能,动态地考虑实际情…...
大数据之国产数据库_OceanBase数据库002_在centos7.9上_安装部署OceanBase001_踩坑指南_亲测可用
部署前最好看一下,部署前的要求, 主要是系统 以及系统内核版本,还有比如清理一下缓存等,按照做一做. 这些都是前置条件. 清一下缓存. 也就是说官网给的前置的条件,都要根据说明去执行一遍,如果不执行可能后面安装会报错. 然后用户最好也去创建一个用户. 注意前置...
【ETCD】【源码阅读】深入解析 EtcdServer.run 函数
EtcdServer.run 是 etcd 的核心运行逻辑之一,负责管理 Raft 状态机的应用、事件调度以及集群的核心操作。本文将逐步从源码层面分析 run 函数的逻辑,帮助读者理解其内部机制和设计思想。 函数签名与关键职责 func (s *EtcdServer) run() {... }关键职责…...
springboot/ssm校内订餐系统Java代码web项目美食外卖点餐配送源码
springboot/ssm校内订餐系统Java代码web项目美食外卖点餐配送源码 基于springboot(可改ssm)vue项目 开发语言:Java 框架:springboot/可改ssm vue JDK版本:JDK1.8(或11) 服务器:tomcat 数据库ÿ…...
floodfill算法
目录 什么是floodfill算法 题目一——733. 图像渲染 - 力扣(LeetCode) 题目二——200. 岛屿数量 - 力扣(LeetCode) 题目三——695. 岛屿的最大面积 - 力扣(LeetCode) 题目四—— 130. 被围绕的区域 …...
【JAVA】六亮增加贴
James Gosling(詹姆斯.高斯林) Java 语言源于 1991 年 4 月,Sun 公司 James Gosling博士 领导的绿色计划(Green Project) 开始启动,此计划最初的目标是开发一种能够在各种消费性电子产品(如机顶盒、冰箱、收音机等)上运行的程序…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
