【Leetcode】746.使用最小花费爬楼梯

题目链接

746. 使用最小花费爬楼梯

题目描述

解题思路

动态规划

每次只能一个阶梯或者两个阶梯，所以要到达第 i 阶，只有两种方案，从第 i-2 阶，或 从 i-1阶到达

• 假设到达第i-2阶的最小花费为p2
• 到达第i-1阶的最小花费为p1
• 第i阶的花费为curr
• 则到达第i阶的最小花费的状态转移为min = Math.min(p1+curr, p2+curr)

动态规划空间优化

第一种方法需要额外申请O(n)的存储空间，我们发现每次值的更新只和前两位相关，所以我们可以利用两个变量存储前两个状态即可。

AC代码

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

优化版本

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int p1 = cost[0];
        int p2 = cost[1];
        int value = 0;
        for(int i = 2; i < cost.length; i++){
            value = cost[i] + Math.min(p1,p2);
            p1 = p2;
            p2 = value;
        }
        return Math.min(p1,p2);
    }
}