746-使用最小花费爬楼梯(Min Cost Climbing Stairs)

原文链接: https://leetcode-cn.com/problems/min-cost-climbing-stairs

英文原文

You are given an integer array cost where cost[i] is the cost of i^th step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

Constraints:

2 <= cost.length <= 1000
0 <= cost[i] <= 999

中文题目

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1：

输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

示例 2：

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

提示：

cost 的长度范围是 [2, 1000]。
cost[i] 将会是一个整型数据，范围为 [0, 999] 。

通过代码

高赞题解

题目要求的是到达第n级台阶楼层顶部的最小花费，可以用动态规划来解，下面一步一步来讲怎样确定状态空间、怎样给出状态转移方程。

理解题意需要注意两点：

第i级台阶是第i-1级台阶的阶梯顶部。

踏上第i级台阶花费cost[i]，直接迈一大步跨过而不踏上去则不用花费。

解法一：

到达第i级台阶的阶梯顶部的最小花费，有两个选择：

先付出最小总花费minCost[i-1]到达第i级台阶（即第i-1级台阶的阶梯顶部），踏上第i级台阶需要再花费cost[i]，再迈一步到达第i级台阶的阶梯顶部，最小总花费为minCost[i-1] + cost[i])；

先付出最小总花费minCost[i-2]到达第i-1级台阶（即第i-2级台阶的阶梯顶部），踏上第i-1级台阶需要再花费cost[i-1]，再迈两步跨过第i级台阶直接到达第i级台阶的阶梯顶部，最小总花费为minCost[i-2] + cost[i-1])；

则minCost[i]是上面这两个最小总花费中的最小值。

minCost[i] = min(minCost[i-1] + cost[i], minCost[i-2] + cost[i-1])。

台阶的数组从0开始计数。可以用-1代表地面，并设cost[-1] = 0。

最小总花费的初始值为：

第0级台阶： minCost[0] = min(cost[-1], cost[0]) = min(0, cost[0]) = 0，

第1级台阶： minCost[1] = min(cost[0], cost[1])。

动态递归代码如下：

[]

class Solution:

    def minCostClimbingStairs(self, cost: List[int]) -> int:

        n = len(cost)

        minCost = [0] * n

        minCost[1] = min(cost[0], cost[1])

        for i in range(2, n):

            minCost[i] = min(minCost[i - 1] + cost[i], minCost[i - 2] + cost[i - 1])

        return minCost[-1]

[]

class Solution {

public:

    int minCostClimbingStairs(vector<int>& cost) {

        int size = cost.size();

        vector<int> minCost(size);

        minCost[0] = 0;

        minCost[1] = min(cost[0], cost[1]);

        for (int i = 2; i < size; i++) {

            minCost[i] = min(minCost[i - 1] + cost[i], minCost[i - 2] + cost[i - 1]);

        }

        return minCost[size - 1];

    }

};

[]

class Solution {

    public int minCostClimbingStairs(int[] cost) {

        int size = cost.length;

        int[] minCost = new int[size];

        minCost[0] = 0;

        minCost[1] = Math.min(cost[0], cost[1]);

        for (int i = 2; i < size; i++) {

            minCost[i] = Math.min(minCost[i - 1] + cost[i], minCost[i - 2] + cost[i - 1]);

        }

        return minCost[size - 1];

    }

}

上面的代码在空间利用上可以再优化一下。只用两个变量保存状态转移方程中前面的两个记录，并不断更新，就可以递推下去，这样空间复杂度就由O(N)变为O(1)了。

代码如下：

[]

class Solution:

    def minCostClimbingStairs(self, cost: List[int]) -> int:

        minCost0, minCost1 = 0, min(cost[0], cost[1])

        for i in range(2, len(cost)):

            minCost = min(minCost1 + cost[i], minCost0 + cost[i - 1])

            minCost0, minCost1 = minCost1, minCost;

        return minCost

[]

class Solution {

public:

    int minCostClimbingStairs(vector<int>& cost) {

        int minCost0 = 0;

        int minCost1 = min(cost[0], cost[1]);

        int minCost;

        for (int i = 2; i < cost.size(); i++) {

            minCost = min(minCost1 + cost[i], minCost0 + cost[i - 1]);

            minCost0 = minCost1;

            minCost1 = minCost;

        }

        return minCost;

    }

};

[]

class Solution {

    public int minCostClimbingStairs(int[] cost) {

        int minCost0 = 0;

        int minCost1 = Math.min(cost[0], cost[1]);

        int minCost = 0;

        for (int i = 2; i < cost.length; i++) {

            minCost = Math.min(minCost1 + cost[i], minCost0 + cost[i - 1]);

            minCost0 = minCost1;

            minCost1 = minCost;

        }

        return minCost;

    }

};

解法二：

到达第i级台阶的阶梯顶部的最小花费，有两个选择：

最后踏上了第i级台阶，最小花费dp[i]，再迈一步到达第i级台阶楼层顶部；
最后踏上了第i-1级台阶，最小花费dp[i-1]，再迈两步跨过第i级台阶直接到达第i级台阶的阶梯顶部。

所以到达第i级台阶的阶梯顶部的最小花费为minCost[i] = min(dp[i], dp[i-1])。

即为了求出到达第i级台阶的阶梯顶部的最小花费，我们先算出踏上第i级台阶的最小花费，用dp[i]表示，再通过min(dp[i], dp[i-1])来求出到达第i级台阶的阶梯顶部的最小花费。

踏上第i级台阶有两种方法：

先踏上第i-2级台阶（最小总花费dp[i-2]），再直接迈两步踏上第i级台阶（花费cost[i]），最小总花费dp[i-2] + cost[i]；

先踏上第i-1级台阶（最小总花费dp[i-1]），再迈一步踏上第i级台阶（花费cost[i]），最小总花费dp[i-1] + cost[i]；

则dp[i]是上面这两个最小总花费中的最小值。

因此状态转移方程是：

dp[i] = min(dp[i-2], dp[i-1]) + cost[i]。

初始条件：

最后一步踏上第0级台阶，最小花费dp[0] = cost[0]。

最后一步踏上第1级台阶有两个选择：

可以分别踏上第0级与第1级台阶，花费cost[0] + cost[1]；
也可以从地面开始迈两步直接踏上第1级台阶，花费cost[1]。

最小值dp[1] = min(cost[0] + cost[1], cost[1]) = cost[1]。

以下是代码：

[]

class Solution:

    def minCostClimbingStairs(self, cost: List[int]) -> int:

        n = len(cost)

        dp = [0] * n

        dp[0], dp[1] = cost[0], cost[1]

        for i in range(2, n):

            dp[i] = min(dp[i - 2], dp[i - 1]) + cost[i]

        return min(dp[-2], dp[-1])

[]

class Solution {

public:

    int minCostClimbingStairs(vector<int>& cost) {

        vector<int> dp(cost.size());

        dp[0] = cost[0];

        dp[1] = cost[1];

        for (int i = 2; i < cost.size(); i++) {

            dp[i] = min(dp[i - 2], dp[i - 1]) + cost[i];

        }

        return min(dp[cost.size() - 2], dp[cost.size() - 1]);

    }

};

[]

class Solution {

    public int minCostClimbingStairs(int[] cost) {

        int[] dp = new int[cost.length];

        dp[0] = cost[0];

        dp[1] = cost[1];

        for (int i = 2; i < cost.length; i++) {

            dp[i] = Math.min(dp[i - 2], dp[i - 1]) + cost[i];

        }

        return Math.min(dp[cost.length - 2], dp[cost.length - 1]);

    }

}

上面的代码在空间利用上可以再优化一下。

注意到状态转移方程中只用到了前面的两个记录，可以不用一维数组，只用两个变量保存前面的两个记录，并不断更新，就可以递推下去，这样空间复杂度就是O(1)了。

更进一步，注意到初始值dp[0] = cost[0]，dp[1] = cost[1]，可以直接复用cost数组来代表dp数组。

代码如下：

[]

class Solution:

    def minCostClimbingStairs(self, cost: List[int]) -> int:

        for i in range(2, len(cost)):

            cost[i] = min(cost[i - 2], cost[i - 1]) + cost[i]

        return min(cost[-2], cost[-1])

[]

class Solution {

public:

    int minCostClimbingStairs(vector<int>& cost) {

        for (int i = 2; i < cost.size(); i++) {

            cost[i] = min(cost[i - 2], cost[i - 1]) + cost[i];

        }

        return min(cost[cost.size() - 2], cost[cost.size() - 1]);

    }

};

[]

class Solution {

    public int minCostClimbingStairs(int[] cost) {

        for (int i = 2; i < cost.length; i++) {

            cost[i] = Math.min(cost[i - 2], cost[i - 1]) + cost[i];

        }

        return Math.min(cost[cost.length - 2], cost[cost.length - 1]);

    }

}

这两种解法的关系：

到达第i级台阶的阶梯顶部的最小花费等于踏上第i级台阶的最小花费与踏上第i-1级台阶的最小花费的最小值：

minCost[i] = min(dp[i], dp[i-1])

将dp[i]的状态转移方程dp[i] = min(dp[i-1], dp[i-2]) + cost[i]代入：


minCost[i] = min(dp[i-1], dp[i])

           = min(min(dp[i-1], dp[i-2]) + cost[i], min(dp[i-2], dp[i-3]) + cost[i-1])

           = min(minCost[i-1] + cost[i], minCost[i-2] + cost[i-1])

这样我们就得到了minCost[i]的状态转移方程。

minCost[i]与dp[i]的关系，还满足minCost[i] = dp[i+1] - cost[i+1]。

统计信息

通过次数	提交次数	AC比率
150879	253355	59.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
爬楼梯	简单

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途