【Leetcode】746. Min Cost Climbing Stairs

da
开始重温dp法， 要秋招了，很菜很慌
爬楼梯，踩在某个台阶上就要支付对应的钱，求需要最少钱爬到楼顶。（注意这里楼顶不是数组的最后一个元素，而是最后一个元素的下一个）

方法1 DP法

每次当前楼梯可以由上一个楼梯或者上上个楼梯爬来，很容易写出递推方程dp[i] = min(dp[i-1], dp[i-2]) + cost[i]，注意起始条件和楼顶条件即可，楼顶可令cost = 0，如果不求楼顶的dp，可以求倒数两个楼梯dp的最小值

class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        cost.append(0)
        dp = [0 for i in range(len(cost))]
        for i in range(len(cost)):
            if i <= 1:
                dp[i] = cost[i]
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
        return dp[-1]

方法2 递归

DP法一般都可以写成递归的形式，最直接的改写如下

class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        cost.append(0)
        return self.helper(cost,len(cost)-1)
        
    def helper(self, cost, N):
        if N <= 1:
            return cost[N]
        else:
            return min(self.helper(cost, N-1), self.helper(cost, N-2)) + cost[N]   

但这样写的坏处就是有很多重复的计算，可以用字典保存已经计算过的元素，改进版如下

class Solution:
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        self.dict = {0: cost[0], 1: cost[1]}
        cost.append(0)
        return self.helper(len(cost)-1,cost)

    def helper(self, N, cost):
        if N in self.dict:
            return self.dict[N]
        else:
            self.dict[N] = min(self.helper(N-1, cost), self.helper(N-2, cost)) + cost[N]
            return self.dict[N]

方法3 改进的DP

方法1 中的dp需要O(n）的存储变量，但实际我们只需要两个变量来存储到当前楼梯和前1楼梯的消耗即可

class Solution2:
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        var,var1  = 0,0
        for c in cost:
            var1, var = var, min(var1,var) + c
        return min(var1, var)