[数据结构与算法]LeetCode力扣746.使用最小花费爬楼梯JAVA

题目

题目链接：
https://leetcode-cn.com/problems/min-cost-climbing-stairs/

分析

题目的意思很明确，可以上一格或两格，因此可以反过来：每个楼梯都是它 下一格 或 下下一格 上来的。

因为每格都有不用的最佳走法，因此贪心策略肯定不太对，应该动态规划！

所以动态方程就因该围绕着 ”下一格“ 和 ”下下一格“ 做决策
什么决策？题目说了，使用最小，所以我们可以得出：

上来这一格的代价=自身代价+min(它下面那格的代价,它下面的下面那格的代价)

细节：因为题目有说cost的长度范围是[2，1000]，所以我们可以直接从第三格开始递推！

代码

    public int minCostClimbingStairs(int[] cost) {
        int lastIndex=cost.length-1;
        for (int i = 2; i <=lastIndex; i++) {
            if(cost[i-1]<=cost[i-2])
                cost[i]+=cost[i-1];
            else
                cost[i]+=cost[i-2];
        }

        return Math.min(cost[lastIndex],cost[lastIndex-1]);
    }