746. Min Cost Climbing Stairs

二刷 07/2022

Version #1 DP with O(1) space

一个比较坑的点就是结束条件是跳出所有的楼梯而不是跳到最后一节楼梯

所以无论是i == 0 || i == 1的base case还是general case，最后都要在prev prev和prev之间再比一遍

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 89.43% of Java online submissions for Min Cost Climbing Stairs.

Memory Usage: 44.2 MB, less than 17.20% of Java online submissions for Min Cost Climbing Stairs.

class Solution {

    public int minCostClimbingStairs(int[] cost) {

        // the cost to get to step i is the min cost between it's two previous steps plus the cost[i]

        if (cost.length <= 2) {

            return Math.min(cost[0], cost[cost.length - 1]);

        }

        int prevprev = cost[0];

        int prev = cost[1];

        for (int i = 2; i < cost.length; i++) {

            int curr = Math.min(prevprev, prev) + cost[i];

            prevprev = prev;

            prev = curr;

        }

        return Math.min(prevprev, prev);

    }

}

一刷
Version #1 DP with O(1) space

class Solution {
    public int minCostClimbingStairs(int[] cost) {
// minimum cost to pay to pass current position
int prevprev = Integer.MAX_VALUE, prev = Integer.MAX_VALUE;
for (int i = 0; i < cost.length; i++) {
if (i == 0 || i == 1) {
prevprev = prev;
prev = cost[i];
} else {
int curr = cost[i] + Math.min(prev, prevprev);
prevprev = prev;
prev = curr;
}
}
return Math.min(prev, prevprev);
}
}