楼主:
Rushia (みけねこ的鼻屎)
2023-10-13 12:26:16https://leetcode.com/problems/min-cost-climbing-stairs/description
746. Min Cost Climbing Stairs
给你一个阵列 cost[] 表示每一层的成本,你需要爬楼梯到楼顶,你每次可以从当前
位置花费 cost[i] 走1步或2步,你从 0 或 1 出发,求出走到 cost.length 最小要
多少 cost。
思路:
1.动态规划,位置 i 当前的成本只能是两种情况:
* 往前一阶的最小成本 + cost[i - 1]
* 往前两阶的最小成本 + cost[i - 2]
在这两种情况取较小值就是当前的最小成本以此类推。
2.因为只需要用到 i - 2 之前的状态,所以用额外两个变量记录就好。
Java Code: