LeetCode.746.使用最小花费爬楼梯

LeetCode.746.使用最小花费爬楼梯

难度：easy

思路就是动态规划：

Java：

动态规划：这里用了数组，还可以用滑动窗口的思想，用三个变量来存储，优化空间复杂度为O(1)；

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

 复杂度分析：

时间复杂度：O(n)

空间复杂度：O(n)