题解 | #最小花费爬楼梯#
最小花费爬楼梯
https://www.nowcoder.com/practice/6fe0302a058a4e4a834ee44af88435c7
- step 1：可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就转移一次状态，最终得到结果。
- step 2：（初始状态） 因为可以直接从第0级或是第1级台阶开始，因此这两级的花费都直接为0.
- step 3：（状态转移） 每次到一个台阶，只有两种情况，要么是它前一级台阶向上一步，要么是它前两级的台阶向上两步，因为在前面的台阶花费我们都得到了，因此每次更新最小值即可，转移方程为：dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])。
凡岛公司福利 319人发布