LeetCode 746 使用最小花费爬楼梯

746.使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

动态规划

1. 确定dp数组（dp table）以及下标的含义：使用 dp[i] 作为动态规划数组，表示到达阶梯 i 的最小花费

2. 确定递推公式：对于要到达第 i 个楼梯，存在两种方案，第一种是从 i-1 向前一步，或者从 i-2 向前两步，对应的递推公式为： dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

3. dp数组如何初始化：对于 dp[0] 应该初始化为0，对于 dp[1] 也可以选择从1开始走，也初始化为0。

4. 确定遍历顺序：此处需要求解的是 dp[n+1] ，显而易见是从前向后遍历

5. 举例推导dp数组：对于 cost = [10,15,20] 那么 dp[2]=min(0+15,0+10)=10 , dp[3]=min(10+20,0+15)=15 验证成立

并且此处当前状态的决策只和前两个状态有关，因此可以在常数空间复杂度内实现。

代码实现：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // 2 <= cost.length无须特殊处理
        int n=cost.size();
        int dp[3];
        dp[0]=0,dp[1]=0;
        for(int i=2;i<=n;i++){
            dp[2]=min(dp[1]+cost[i-1],dp[0]+cost[i-2]);
            dp[0]=dp[1];
            dp[1]=dp[2];
        }
        return dp[2];
    }
};