动态规划|746.使用最小花费爬楼梯

力扣题目链接

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()];
    }
};

思路

在力扣修改了题目描述下,我又重新修改了题解

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

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

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

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

对于dp数组的定义,大家一定要清晰!

  1. 确定递推公式

可以有两个途径得到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]);

  1. 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;

  1. 确定遍历顺序

最后一步,递归公式有了,初始化有了,如何遍历呢?

本题的遍历顺序其实比较简单,简单到很多同学都忽略了思考这一步直接就把代码写出来了。

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

但是稍稍有点难度的动态规划,其遍历顺序并不容易确定下来。 例如:01背包,都知道两个for循环,一个for遍历物品嵌套一个for遍历背包容量,那么为什么不是一个for遍历背包容量嵌套一个for遍历物品呢? 以及在使用一维dp数组的时候遍历背包容量为什么要倒序呢?

这些都与遍历顺序息息相关。当然背包问题后续「代码随想录」都会重点讲解的!

  1. 举例推导dp数组

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

如果大家代码写出来有问题,就把dp数组打印出来,看看和如上推导的是不是一样的。

 

自己的思路: 

1.当你往上跳时才花费

感觉和之前2题的套路都很像

重要的就是要搞懂dp数组的含义!!!

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【面试必备】MySQL索引是什么?怎么设计索引?

在后端面试中&#xff0c;MySQL的索引是一个常见问题&#xff0c;尤其是最近掀起了去Oracle的风向。作为一个很宽泛的面试题&#xff0c;不仅考验对MySQL整体知识的了解&#xff0c;也方便面试官随着我们的回答逐渐往下延伸问题。众所周知&#xff0c;面试问题的答案&#xff0…

【2024年MathorCup数模竞赛】C题赛题与解题思路

2024年MathorCup数模竞赛C题 题目 物流网络分拣中心货量预测及人员排班背景求解问题 解题思路问题一问题二问题三问题四 本次竞赛的C题是对物流网络分拣中心的货量预测及人员排班问题进行规划。整个问题可以分为两个部分&#xff0c;一是对时间序列进行预测&#xff0c;二是对人…

C++list模拟实现

Clist模拟实现 list接口总结结点类的模拟实现迭代器的模拟实现迭代器模板参数迭代器类中的构造函数迭代器类中的运算符重载operator和operator - -operator&#xff01; 和operatoroperator*operator->总览 list 类构造函数拷贝构造函数赋值运算符重载operatorclear&#xf…

高精度定时器中 single-shot 计数模式不工作

1. 问题提出 客户使用 STM32G474 的高精度定时器&#xff0c;基于 CubeMX 进行外设配置与代码生成&#xff0c;将某个子定时器的计数方式设置为 retriggerable single shot 方式&#xff0c;发现该子定时器无 PWM 输出&#xff0c;在调试模式下发现该子定时器的计数器一直为 0…

2024MathorCup(妈妈杯) C题完整思路+数据集+完整代码+高质量成品论文

C题物流网络分中心货量预测及人员排班 &#xff08;完整的资料数据集代码在文末&#xff09; 电商物流网络在订单履约中由多个环节组成&#xff0c;其中&#xff0c;分拣中心作为网络的中 间环节&#xff0c;需要将包裹按照不同流向进行分拣并发往下一个场地&#xff0c;最终使…

「每日跟读」英语常用句型公式 第10篇

「每日跟读」英语常用句型公式 第10篇 1. It goes without saying that __ 毋庸置疑的是 ______ It goes without saying that hard work pays off(毋庸置疑的是&#xff0c;努力工作会有回报) It goes without saying that health is the most important wealth(毋庸置疑的…

C++第十五弹---string基本介绍(一)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】 目录 1、什么是STL 2、STL的版本 3、STL的六大组件 4、STL的重要性 5、如何学习STL 6、STL的缺陷 7、为什么学习string类 7.1、C语言中的字符串…

节省30%成本,宝马使用 NVIDIA Omniverse 构造的数字孪生虚拟汽车工厂,实现降本增效

在数字化转型过程中&#xff0c;汽车制造商宝马集团将工业 AI 的力量运用到整个生产网络&#xff0c;与NVIDIA Omniverse平台共同构建并运行工业元宇宙应用。 宝马集团董事Milan Nedeljković在GTC主题演讲会中&#xff0c;与NVIDIA创始人兼首席执行官黄仁勋共同展示了Omniver…

YOLOv8打印模型结构配置信息并查看网络模型详细参数:参数量、计算量(GFLOPS)

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…

LeetCode-1143. 最长公共子序列【字符串 动态规划】

LeetCode-1143. 最长公共子序列【字符串 动态规划】 题目描述&#xff1a;解题思路一&#xff1a;动规五部曲解题思路二&#xff1a;1维DP解题思路三&#xff1a;0 题目描述&#xff1a; 给定两个字符串 text1 和 text2&#xff0c;返回这两个字符串的最长 公共子序列 的长度。…

TSINGSEE青犀AI智能分析网关V4吸烟/抽烟检测算法介绍及应用

抽烟检测AI算法是一种基于计算机视觉和深度学习技术的先进工具&#xff0c;旨在准确识别并监测个体是否抽烟。该算法通过训练大量图像数据&#xff0c;使模型能够识别出抽烟行为的关键特征&#xff0c;如烟雾、手部动作和口部形态等。 在原理上&#xff0c;抽烟检测AI算法主要…

【目标检测数据集】城市街道垃圾堆相关数据集

一、GarbageOverflow&#xff1a;城市街道垃圾堆数据集 该垃圾堆数据集是通过爬虫从网上进行爬取得到的&#xff0c;一共包含1188张图片&#xff0c;有2个类别&#xff0c;分别为[overflow, No Overflow]&#xff0c;两个标签的数量分别为1734个标签和414个标签。部分数据集及…

中国历年GDP统计-探数API统计

数据介绍 时间维度&#xff1a;1978年-2021年 单位&#xff1a;亿元 该数据来源于国家统计局发布的中国统计年鉴2021&#xff0c;为按当年价格计算的中国历年GDP以及人均GDP。 数据说明&#xff1a; 数据来源于国家统计局。

【更新】全国省级-新质生产力数据集(2010-2022年)

01、数据简介 新质生产力&#xff0c;又称为新型生产力&#xff0c;是指在现代科技和经济社会发展的推动下&#xff0c;由新的生产要素、生产方式、生产关系等构成的具有新质特点的生产力。这种生产力突破了传统生产力的局限&#xff0c;具有更高的效率和创造力&#xff0c;是…

题目 2694: 蓝桥杯2022年第十三届决赛真题-最大数字【暴力解法】

最大数字 原题链接 &#x1f970;提交结果 思路 对于每一位&#xff0c;我我们都要尽力到达 9 所以我们去遍历每一位, 如果是 9 直接跳过这一位 如果可以上调到 9 我们将这一位上调到 9 &#xff0c;并且在a 中减去对应的次数 同样的&#xff0c;如果可以下调到 9&#xff0c;我…

黄金基金和黄金有什么区别?

黄金基金本质上是一种投资工具&#xff0c;它通过间接投资黄金或与其紧密相关的金融衍生品来反映黄金市场的表现。不同于直接持有实物黄金&#xff0c;投资者购买黄金基金并不涉及实体黄金的保管问题&#xff0c;而是将资金交由专业的基金管理人管理&#xff0c;由他们代表投资…

Input DropDown 拼接成 select组件(基于antd和react)

前言&#xff1a;为什么不直接用select&#xff0c;还要舍近求远搞inputdropdown这种缝合怪&#xff0c;是因为antd的select不支持选中项再编辑&#xff0c;效果如图 比如&#xff1a;选中的lucy文案变成了placeholder不能再编辑了 封装此组件虽然比较简单&#xff0c;但还是有…

一文读懂Partisia Blockchain,被严重低估的隐私区块链生态

在今年 3 月&#xff0c;隐私公链 Partisia Blockchain 迎来了重要的进展&#xff0c;该生态通证 $MPC 上线了交易所&#xff0c;目前 $MPC 通证可以在 Kucoin、Gate、BitMart、Bitfinex、Bitture 等平台交易&#xff0c;并将在不久后上线 MEXC 平台。 在上个月上线市场至今&am…

中颖51芯片学习4. 可编程计数器阵列PCA0

中颖51芯片学习4. 可编程计数器阵列PCA0 一、PCA介绍1. PCA简介2. SH79F9476的PCA0特性3. PCA0 功能4. 时钟5. PCA0原理框图6. 工作方式 二、PCA0寄存器1. PCA0标志寄存器2. PCA使能寄存器3. PCA0方式寄存器4. P0CPMn PCA捕捉/比较寄存器5. P0FORCE强制输出控制寄存器6. PCA0计…

期货量化交易软件:MQL5 中的范畴论 (第 15 部分)函子与图论

概述 在上一篇文章中&#xff0c;我们目睹了前期文章中涵盖的概念&#xff08;如线性序&#xff09;如何视作范畴&#xff0c;以及为什么它们的“态射”在与其它范畴相关时即构成函子。在本文中&#xff0c;我们赫兹量化软件将阐述来自前期文章中的概括&#xff0c;即通过查看…