[代码随想录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) 开始启动,此计划最初的目标是开发一种能够在各种消费性电子产品(如机顶盒、冰箱、收音机等)上运行的程序…...
自建链接管理服务OtterLink:从部署到实战的完整指南
1. 项目概述:一个链接管理的“瑞士军刀” 最近在折腾个人知识库和内容分发,发现一个痛点:手头攒了太多链接。技术文章、工具网站、项目仓库、临时笔记链接……散落在浏览器书签、聊天记录、备忘录里,时间一长要么找不到ÿ…...
不止于Kali:在Ubuntu、Debian上给COMFAST CF-812AC无线网卡装RTL8812BU驱动的通用教程
跨平台兼容:Ubuntu/Debian系统安装COMFAST CF-812AC无线网卡驱动全指南 COMFAST CF-812AC作为一款高性价比的双频无线网卡,凭借Realtek RTL8812BU芯片的稳定表现,成为许多开发者和技术爱好者的首选。然而,当用户从Kali Linux转向U…...
图像理解的底层逻辑:从像素到语义的三层跃迁
1. 这不是“看图说话”,而是让机器学会“看见”的底层逻辑 你有没有想过,当手机相册自动给你把“猫”和“狗”的照片分到不同相册里,或者修图App能一键抠出人像边缘、连发丝都清晰分明,背后到底发生了什么?很多人以为A…...
Android端ChatGPT客户端开发:MVVM架构与OpenAI API集成实践
1. 项目概述与核心价值最近在折腾移动端AI应用开发,发现一个挺有意思的开源项目——icecoins/ChatGPT_Android。这名字一看就懂,一个在Android平台上实现ChatGPT功能的客户端。但如果你以为这只是个简单的WebView套壳,那就太小看它了。我花了…...
从零到一:使用DaVinci Developer进行AUTOSAR SWC设计与ECU集成
1. 认识AUTOSAR与DaVinci Developer工具 第一次接触汽车电子开发的朋友,可能会被AUTOSAR这个术语吓到。其实它就像汽车软件界的"普通话"——各家厂商用统一的标准交流,避免出现"鸡同鸭讲"的情况。而DaVinci Developer就是Vector公司…...
CDFControl工具详解,搞定云桌面黑屏、卡顿、随机掉线疑难故障
一 前言 在企业Citrix云桌面运维工作中,我们经常遇到一类无明确报错、间歇性复现的疑难故障。常规Windows事件查看器日志干净无报错,常规DDC控制台监控无异常,但终端用户会频繁出现登录黑屏、会话卡顿、虚拟机随机掉线、VDA注册超时等问题。 很多运维人员遇到此类问题只能…...
别再只调包了!用PyTorch从零手搓一个Unet,搞懂语义分割的每个细节
从零构建Unet:深入解析语义分割的代码实现与设计哲学 在计算机视觉领域,语义分割一直是极具挑战性的任务之一。不同于简单的图像分类,语义分割需要模型对图像中的每一个像素进行分类,这要求模型既要理解全局上下文信息,…...
Go语言规则同步器airulesync:自动化聚合与更新网络过滤规则
1. 项目概述:一个自动同步上游规则的“规则同步器”如果你和我一样,长期在维护自己的网络过滤规则集,无论是用于广告屏蔽、隐私保护还是内容过滤,那么你一定对“规则更新”这件事深有体会。手动去各个开源项目的主页查看更新、下载…...
AI文本处理利器:MCP服务器实现结构化信息提取与智能解析
1. 项目概述:一个为AI应用注入结构化文本处理能力的MCP服务器 最近在折腾AI应用开发,特别是那些需要让大语言模型(LLM)与外部工具和数据源打交道的场景,我发现一个核心痛点:如何高效、可靠地将非结构化的文…...
Android本地AI语音助手Cliff:开源、离线与可定制的边缘计算实践
1. 项目概述:Cliff,一个运行在Android上的本地化AI语音助手最近在GitHub上看到一个挺有意思的项目,叫“Cliff-Android-Voice-Assistant”。光看名字,你大概能猜到它是一个给安卓设备用的语音助手。但和Siri、小爱同学、Google Ass…...
