746. Min Cost Climbing Stairs最小花费上楼梯Java

给定一个整数数组cost，其中cost[i]是楼梯上的步骤成本。支付费用后，您可以爬上一两步。
您可以从步骤与指数无论是启动0，或索引步骤1返回到达楼层顶部的最低成本。

示例 1：
输入： cost = [10, 15 ,20]
输出： 15
解释：你将从索引 1 开始。

• 支付 15 并爬两步到达顶部。
  总成本是15。

示例 2：
输入： cost = [ 1 ,100, 1 ,1, 1 ,100, 1 , 1 ,100, 1 ]
输出： 6
解释：你将从索引 0 开始。

• 支付 1 并爬两步到达指数 2。
• 支付 1 并爬两步到达指数 4。
• 支付 1 并爬两步到达指数 6。
• 支付 1 并爬一级达到指数 7。
• 支付 1 并爬两步到达指数 9。
• 支付 1 并爬上一步到达顶部。
  总成本是6。

约束：
2 <= cost.length <= 1000
0 <= cost[i] <= 999

思路
和70题爬楼梯差不多, 当前步数等于前两个的最小值+现在的cost。curStep=Min(preStep+prepreStep)+curCost

1. 因为题中说cost.length长度>=2, 所以动态规划(Dynamic Programming)的时候i从1开始, 定义pre1=0和pre2=cost[0]
2. 选择前两个中的小的+curCost, 然后将pre1和pre2更新
3. 最后返回的时候也要返回pre1和pre2中最小的那个

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int pre1 = 0, pre2 = cost[0];
        for (int i = 1; i < cost.length; i++) {
            int temp = Math.min(pre1,pre2)+cost[i];
            pre1 = pre2;
            pre2=temp;
        }
        return Math.min(pre1,pre2);
    }
}

时间复杂度O(n)因为只遍历数组一次