使用最小花费爬楼梯

发表于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

LeetCode每日一题，746. Min Cost Climbing Stairs

先看题目描述

r09mJe.png

大意就是给定一个数组代表爬每级阶梯的代价，爬阶梯时可以选择从 0 级阶梯开始，也可以从 1 级阶梯开始，每付出一次代价后，可以往上爬一级阶梯，也可以爬两级阶梯，问爬到阶梯顶部的最小花费是多少

算法和思路

动态规划

这题挺简单，用动态规划就可以，dp[i] 代表从第 i 级阶梯爬到楼梯顶的最小花费

状态转移方程为：dp[i] = cost[i] + min{dp[i + 1]，dp[i + 2]}

由于爬阶梯可以从 0 级阶梯或 1 级阶梯开始，最后返回 dp[0] 和 dp[1] 中的最小值即可

算法源码

动态规划

实现动态规划算法的代码，只要状态转移方程没问题，并且注意好初始条件和边界条件，基本实现的代码都不会出问题

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len];
        dp[len - 1] = cost[len - 1];
        dp[len - 2] = cost[len - 2];
        for (int i = len - 3; i >= 0; i--) {
            dp[i] = cost[i] + Math.min(dp[i + 1], dp[i + 2]);
        }
        return Math.min(dp[0], dp[1]);
    }
}

下面是用滚动数组的思想优化空间的写法的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int nnext = cost[len - 1];
        int next = cost[len - 2];
        int cur;
        for (int i = len - 3; i >= 0; i--) {
            cur = cost[i] + Math.min(next, nnext);
            nnext = next;
            next = cur;
        }
        return Math.min(next, nnext);
    }
}