算法日常・每日刷题--＜动态规划＞3-北京尧图网络

746. 使用最小花费爬楼梯 - 力扣LeetCode题目描述给你一个整数数组cost其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。你可以选择从下标为0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。注意楼梯顶部不是 cost 数组里的台阶是数组末尾之后的位置。例如 cost 长度为 n要走到 n 的位置才算登顶。示例输入cost [10,15,20]输出15解释从下标 1 开始付 15直接跨两步到达楼顶。动态规划五部曲分析做动态规划题目固定 5 步思考dp 数组含义、递推公式、初始化、遍历顺序、结果返回。1. dp 数组定义dp[i]到达第 i 阶台阶所需要的最小花费。i 的范围0 ~ nn cost.size()dp[n]代表到达楼顶。2. 状态转移公式想要到达第i位置只有两种来源从i‑1台阶爬上来到达i‑1的花费dp[i‑1] 登上i‑1台阶要付的钱cost[i‑1]从i‑2台阶爬上来到达i‑2的花费dp[i‑2] 登上i‑2台阶要付的钱cost[i‑2]取得两者的最小值即可3. dp 数组初始化题目允许起点选 0 或者 1 台阶站在 0、1 台阶本身不需要花钱花钱是离开这个台阶往上走的时4. 遍历顺序每一个dp[i]依赖前面dp[i‑1]、dp[i‑2]所以从左到右循环i 从 2 一直到 n。5. 返回结果楼顶是第 n 位置返回dp[n]。class Solution { public: int minCostClimbingStairs(vectorint cost) { // 定义dp数组,dp推到公式,初始化,从左往右填,返回值 int ncost.size(); vectorintdp(n1); dp[0]0; dp[1]0; for(int i2;in1;i) { dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]); } return dp[n]; } };候。

算法日常・每日刷题--＜动态规划＞3

相关推荐

不花一分钱搜索 X：insane-search 双路关键词发现与推文再验证原理

HTTPS 部署实战：未备案域名 + 非标端口的完整方案

数据库连接池如何热轮换凭据不中断：安当SMS的落地实践

更多资讯

贝叶斯公式计算器：从原理到工程落地的Python实现

虚拟偶像舞蹈视频制作全流程：从动作生成到渲染合成的技术拆解

Hadoop实现商品推荐系统：MapReduce协同过滤实战

水稻稻穗YOLO数据集：6108张开箱即用训练图

纯Python实现SMPLify人体三维参数化建模流水线

电脑玩手机游戏模拟器哪个好电脑玩手机游戏什么模拟器好

今日更新

45个经典Linux面试题：从命令到网络排障的完整考点解析

SAP生产预留实战指南：MB21/MB23/MB25协同与MRP集成

编译原理实验：递归下降分析器消除左递归与避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？