算法日常・每日刷题--＜动态规划＞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]; } };候。