解题思路

题目说从一个台阶向上爬需要付出cost[i]的费用，而每次只能爬1~2层台阶。

根据示例得出楼顶为cost[len(cost)]也就数组外。

由于每次只能爬1~2层台阶，那么我们可以直接从下标为3的地方开始顺序遍历。

递推公式：dp[i] = min(dp[i - 1], dp[i - 2])

每次取前两个台阶的最小费用，这样就能达到最小费用了。

代码

Python

1
2
3
4
5
6
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost) == 2: return min(cost)
        for i in range(2, len(cost)):
            cost[i] += min(cost[i - 1], cost[i - 2])
        return min(cost[-1], cost[-2])

C++

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if (cost.size() == 2) return min(cost[1], cost[0]);
        for (int i = 2; i < cost.size(); i++) {
            cost[i] += min(cost[i - 1], cost[i - 2]);
        }
        return min(cost[cost.size() - 1], cost[cost.size() - 2]);
    }
};

GO

func minCostClimbingStairs(cost []int) int {
    if len(cost) == 2 {return min(cost[0], cost[1])}
    n := len(cost)
    for i := 2; i < n; i++ {
        cost[i] += min(cost[i - 1], cost[i - 2])
    }
    return min(cost[n - 1], cost[n - 2])
}

func min(a int, b int) int {
    if a <= b {return a}
    return b
}