题解 | #最小花费爬楼梯#

符合DP一模型三特征，因此用DP来解。 关键在于找到状态转移方程，假设x(n)为爬到楼梯第n阶台阶的最小花费。需要注意一下题目里爬到楼顶是需要爬到len(cost)这个index的台阶的，因此为了方便我们往cost最后加一个0，作为楼梯顶。 状态转移方程为：

$x(n)=min\{(x(n-1)+cost[n-1]),(x(n-2)+cost[n-2])\}x(n)=min\backslash \{(x(n-1)+cost[n-1]),\; (x(n-2)+cost[n-2])\backslash \}$

也就是说要爬到第n阶只有两种方法，先爬到n-1阶，然后从n-1阶往上爬，先爬到n-2阶，然后从n-2阶往上爬。因此爬到第n阶的最小费用就是爬到n-1在往上爬和爬到n-2在往上爬的费用的较小的那一个。得到状态转移方程后就容易解了。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param cost int整型一维数组 
# @return int整型
#
class Solution:
    def minCostClimbingStairs(self , cost) -> int:
        # write code here
        cost.append(0)
        leng = len(cost)
        if leng == 2 or leng == 3:
            return 0
        xn_1 = 0
        xn_2 = 0
        for i in range(2,leng):
            xn = min((xn_1+cost[i-1]) , (xn_2+cost[i-2]))
            xn_2 = xn_1
            xn_1 = xn
        return xn

cost=[1,100,1,1,1,90,1,1,80,1]
print(Solution().minCostClimbingStairs(cost))