LeetCode使用最小花费爬楼梯----dp问题

题目：给你一个整数数组cost，其中cost[i]是从楼梯第个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬—个或者两个台阶。
你可以选择从下标为0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

示例如下：

这道题和青蛙爬楼梯差不多，可以参考下dp问题的常用思路步骤 

动态规划问题三步走：

第一步骤：定义数组元素的含义

第二步骤：找出数组元素之间的关系式

第三步骤：找出初始值

用画图写的大概思路，带举例

dp[i]表示到达i的最小花费
cost[i]表示从第i个楼梯上爬需要的费用

i-1楼梯，花费cost[i-1]可以到达下标i

当2<isn时(因为一次可以选择走1阶或者2阶)，可以从下标i-1使用cost[i一1]的花费达到下标i，或者从下标i-2使用costi-2]的花费达到下标i。为了使总花费最小,dp[i]应取上述两项的最小值。

举例:i等于2时，到
达2有两种办法
下标O走两阶或者下标1走一阶
dpli]表示你到第0阶或者第1阶的最小花费，因为这两个台阶是初始台阶，可以选择，所以dp[1/0]都为O，只需要考虑cost[0]和cost[1]谁大cost[0]和cost[1]都可以通过支付费用到达第二阶台阶上写的数字是设置的费用，那么就是0+2和O+1取最小得知dp2=1
同理i=3的时候可以通过第一阶徒2或者第二阶走1也就是0+1和1+3取最小值得知dp3 = 1
直到到达顶端即dp数组的终点返回dp终点即可。

 代码如下：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}

这道题通过分析还可以发现，每个元素只和上个元素和上上个元素有关，可以思考是否符合滚动数组。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        int prev = 0, curr = 0;//初始化
        for (int i = 2; i <= n; i++) {
            int next = min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;//滚动
            curr = next;//滚动
        }
        return curr;
    }
};