746. Min Cost Climbing Stairs

https://leetcode.com/problems/min-cost-climbing-stairs/

Easy

问题描述：

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

1. cost will have a length in the range [2, 1000].
2. Every cost[i] will be an integer in the range [0, 999].

题目分析：

这是一道“爬楼梯”的问题，这个楼梯每次可以走一格或者两格，每一格都有对应的花费，从第一格或者第二格的位置出发，我们需要找到登顶时的最低花费。

这一题是一个简单的动态规划问题，有两种走法可以到达第i格：从第i-1格出发，或者从第i-2格出发。因此，到达第i格的最低花费为：dp[i]=min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])，需要注意，第一格和第二格的花费均为0。

代码：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * (len(cost) + 1)
        for i in range(2, len(cost) + 1):
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])        
        return dp[len(cost)]

补充：

上述代码的空间复杂度为O(n)，可以通过用三个变量保存每一步的花费来减少空间占用，代码如下：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n=len(cost)
        first_cost, second_cost = 0, 0
        for i in range(2, n+1):
            third_cost = min(second_cost+cost[i-1], first_cost+cost[i-2])
            first_cost = second_cost
            second_cost = third_cost
        return third_cost