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

DAY38 动态规划 + 509. 斐波那契数 + 70. 爬楼梯 + 746. 使用最小花费爬楼梯

动态规划理论

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

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

状态转移公式(递推公式)是很重要,但动规不仅仅只有递推公式。

对于动态规划问题,我将拆解为如下五步曲,这五步都搞清楚了,才能说把动态规划真的掌握了!

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

509. 斐波那契数

题目要求:斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给你n ,请计算 F(n) 。

思路

动规五部曲:

这里我们要用一个一维dp数组来保存递归的结果

  1. 确定dp数组以及下标的含义 dp[i]的定义为:第i个数的斐波那契数值是dp[i]
  2. 确定递推公式 状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
  3. dp数组如何初始化 dp[0] = 0; dp[1] = 1;
  4. 确定遍历顺序,从前向后遍历
  5. 举例推导 根据公式当n=10时,数列为0 1 1 2 3 5 8 13 21 34 55
class Solution {
public:int fib(int n) {if (n <= 1) return n;vector<int> dp(n+1);dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; ++i) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
};

70. 爬楼梯

题目要求:

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

思路

上第i个台阶的方法数=上第i-1个台阶的方法数(爬1个台阶)+上第i-2个台阶的方法数(爬2个台阶)

class Solution {
public:int climbStairs(int n) {if (n<=1) return n;int dp[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];}
};

746. 使用最小花费爬楼梯

题目要求:数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。

每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯。

思路

修改之后的题意就比较明确了,题目中说 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于 跳到 下标 0 或者 下标 1 是不花费体力的, 从 下标 0 下标1 开始跳就要花费体力了。

  • 确定dp数组以及下标的含义

使用动态规划,就要有一个数组来记录状态,本题只需要一个一维数组dp[i]就可以了。

dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]

  • 确定递推公式

可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢?

一定是选最小的,所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

  • dp数组如何初始化

看一下递归公式,dp[i]由dp[i - 1],dp[i - 2]推出,既然初始化所有的dp[i]是不可能的,那么只初始化dp[0]和dp[1]就够了,其他的最终都是dp[0]dp[1]推出。

那么 dp[0] 应该是多少呢? 根据dp数组的定义,到达第0台阶所花费的最小体力为dp[0],那么有同学可能想,那dp[0] 应该是 cost[0],例如 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 的话,dp[0] 就是 cost[0] 应该是1。

这里就要说明本题力扣为什么改题意,而且修改题意之后 就清晰很多的原因了。

新题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的,但从 第0 个台阶 往上跳的话,需要花费 cost[0]。

所以初始化 dp[0] = 0,dp[1] = 0;

  • 确定遍历顺序

因为是模拟台阶,而且dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了。

  • 举例推导dp数组

拿示例2:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ,来模拟一下dp数组的状态变化,如下:

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size() + 1);dp[0] = 0;dp[1] = 0;for (int i = 2; i <= cost.size(); ++i) {dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);}return dp[cost.size()];}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
  • 还可以优化空间复杂度,因为dp[i]就是由前两位推出来的,那么也不用dp数组了,优化方法和上一题同理。

相关文章:

DAY38 动态规划 + 509. 斐波那契数 + 70. 爬楼梯 + 746. 使用最小花费爬楼梯

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

Redis快速上手篇七(集群-一台虚拟机六个节点)

​​​​​​http://t.csdnimg.cn/S0NpK与上篇六个虚拟机配置基本一样有不懂可以看上篇配置实例 集群搭建 根据上篇文章&#xff0c;本篇只着重于小方面的配置差别 配置集群一般不要设置密码 1.搭建一台虚拟机后再安装目录下新建文件夹 redis_cluster 2.在文件夹内创建六个文…...

社恐了怎么办?如何改变社交恐惧症?

社恐这个词已经算是普及了&#xff0c;自嘲自己是社恐的人真的挺多的&#xff0c;好像一句我社恐了就能解析很多问题&#xff0c;其实真正的社恐远比我们想象的要痛苦多了&#xff0c;社恐能被更多人认识到本来是件好事&#xff0c;但是过于的用社恐来给自己贴标签&#xff0c;…...

HiQPdf Library for .NET - HTML to PDF Crack

HiQPdf Library for .NET - HTML 到 PDF 转换器 .NET Core&#xff0c;用于 .NET 的 HiQPdf HTML 到 PDF 转换器 &#xff1a;HiQPdf HTML to PDF Library for .NET C# 和 HTML to PDF .NET Core 为您提供了一个现代、快速、灵活且强大的工具&#xff0c;只需几行代码即可创建复…...

ES6中Set集合

ES6中的Set是一种数据结构&#xff0c;类似于数组&#xff0c;但是它的值都是唯一的。它是通过一组有序的、由唯一元素组成的集合实现的&#xff0c;不允许重复项。Set可以用于存储任何类型的数据&#xff0c;包括原始类型和复合类型&#xff0c;如对象和数组。 Set有以下特点…...

论坛介绍 | COSCon'23 开源文化(GL)

众多开源爱好者翘首期盼的开源盛会&#xff1a;第八届中国开源年会&#xff08;COSCon23&#xff09;将于 10月28-29日在四川成都市高新区菁蓉汇举办。本次大会的主题是&#xff1a;“开源&#xff1a;川流不息、山海相映”&#xff01;各位新老朋友们&#xff0c;欢迎到成都&a…...

【httpd】 Apache http服务器目录显示不全解决

文章目录 1. 文件名过长问题1.1 在centos中文件所谓位置etc/httpd/conf.d/httpd-autoindex.conf1.2 在配置文件httpd-autoindex.conf中的修改&#xff1a;1.3 修改完成后重启Apache&#xff1a; 1. 文件名过长问题 1.1 在centos中文件所谓位置etc/httpd/conf.d/httpd-autoindex…...

笔记本电脑搜索不到wifi6 无线路由器信号

路由器更换成wifi6 无线路由器后&#xff0c;手机能搜索到这个无线信号&#xff0c;但是笔记本搜索不到这个无线信号&#xff0c;后网上搜索后发现是无线网卡驱动问题&#xff0c;很多无线网卡使用的是Intel芯片&#xff0c;Intel就此发布了公告&#xff0c;升级驱动就可以彻底…...

js获取input?

在JavaScript中&#xff0c;获取输入框&#xff08;通常指的是HTML的<input>元素&#xff09;的值有多种方法。以下是其中的一些&#xff1a; 通过ID获取&#xff1a; javascriptvar inputValue document.getElementById(inputId).value; 这里&#xff0c;inputId 是…...

STM32 CAN使用

STM32 CAN使用 简介各种通讯接口对比报文总线上的报文信息表示为几种固定的赖类型数据帧列表模式掩码模式配置CAN配置参数位时序 简介 控制器局域网CAN&#xff08;Controller Area Network)是由德国博世公司为汽车应用而开发的多主机局部网络&#xff0c;用于汽车的监测和控制…...

安全和便捷:如何将运营商二要素API应用于实名制管理中

引言 随着互联网的快速发展&#xff0c;数字化身份验证和实名制管理变得越来越重要。在金融、电子商务、社交媒体等领域&#xff0c;确保用户身份的安全和准确性至关重要。运营商二要素核验API成为了实名制管理的有力工具&#xff0c;它不仅能够提供高水平的安全性&#xff0c…...

leetcode-二叉树

B树和B树的区别 B树&#xff0c;也即balance树&#xff0c;是一棵多路自平衡的搜索树。它类似普通的平衡二叉树&#xff0c;不同的一点是B树允许每个节点有更多的子节点。 B树内节点不存储数据&#xff0c;所有关键字都存储在叶子节点上。B树&#xff1a; B树&#xff1a; 二叉…...

【鸿蒙软件开发】ArkTS基础组件之TextTimer(文本显示计时)、TimePicker(时间选择)

文章目录 前言一、TextTimer1.1 子组件1.2 接口参数TextTimerController 1.3 属性1.4 事件1.5 示例代码 二、TimePicker2.1 子组件2.2 接口参数 2.3 属性2.4 事件TimePickerResult对象说明 2.5 示例代码 总结 前言 通过文本显示计时信息并控制其计时器状态的组件。 时间选择组…...

pytorch 笔记:KLDivLoss

1 介绍 对于具有相同形状的张量 ypred​ 和 ytrue&#xff08;ypred​ 是输入&#xff0c;ytrue​ 是目标&#xff09;&#xff0c;定义逐点KL散度为&#xff1a; 为了在计算时避免下溢问题&#xff0c;此KLDivLoss期望输入在对数空间中。如果log_targetTrue&#xff0c;则目标…...

父子项目打包发布至私仓库

父子项目打包发布至私仓库 1、方法一 在不需要发布至私仓的模块上添加如下代码&#xff1a; <plugin><groupId>org.apache.maven.plugins</groupId><artifactId>maven-deploy-plugin</artifactId><configuration><skip>true</s…...

汽车网络安全--ECU的安全更新

目前,汽车ECU的软件更新可以总结分成三大类: 工厂刷写模式:工厂大批量刷写或者升级,一般在出厂用; 工程模式:4S店、工厂等专业人员进行的ECU固件更新,通常是动力、转向、车控等; 车主模式:车主根据云端推送信息,通过IVI进行应用软件更新;目前也有趋势通过这种方式刷…...

NLP之搭建RNN神经网络

文章目录 代码展示代码意图代码解读知识点介绍1. Embedding2. SimpleRNN3. Dense 代码展示 # 构建RNN神经网络 from tensorflow.keras.models import Sequential from tensorflow.keras.layers import Dense, SimpleRNN, Embedding import tensorflow as tfrnn Sequential() …...

Android问题笔记四十三:JNI 开发如何快速定位崩溃问题

点击跳转>Unity3D特效百例点击跳转>案例项目实战源码点击跳转>游戏脚本-辅助自动化点击跳转>Android控件全解手册点击跳转>Scratch编程案例点击跳转>软考全系列 &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分享&…...

机器学习 | 决策树算法

一、决策树算法概述 1、树模型 决策树&#xff1a;从根节点开始一步步走到叶子节点(决策)。所有的数据最终都会落到叶子节点&#xff0c;既可以做分类也可以做回归。 在分类问题中&#xff0c;表示基于特征对实例进行分类的过程&#xff0c;可以认为是if-then的集合&#xff0…...

javascript中各种风骚的代码

1.判断数值符号是否相同 function numericSymbolsIsEqual(x: number, y: number): boolean {return (x ^ y) > 0}console.log(numericSymbolsIsEqual(1, 1))console.log(numericSymbolsIsEqual(-1, 1))console.log(numericSymbolsIsEqual(1, -1))console.log(numericSymbols…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...