Interview 150
Min Cost Climbing Stairs
- Problem
- LC 746
- File
- interview150_LC746MinCostClimbingStairs.java
- Path
- pkg5leetcode/interview150/interview150_LC746MinCostClimbingStairs.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC746MinCostClimbingStairs.java
- Approach
- DP min cost to reach each step from prior two.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Min Cost Climbing Stairs | LC 7465 * APPROACH: DP min cost to reach each step from prior two.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class interview150_LC746MinCostClimbingStairs {9 static int minCostClimbingStairs(int[] cost) {10 int a = 0, b = 0;11 for (int i = 2; i <= cost.length; i++) {12 int c = Math.min(a + cost[i - 2], b + cost[i - 1]);13 a = b;14 b = c;15 }16 return b;17 }18 19 public static void main(String[] args) {20 check(minCostClimbingStairs(new int[]{10, 15, 20}) == 15, "case1");21 check(minCostClimbingStairs(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}) == 6, "case2");22 System.out.println("all tests passed");23 }24 25 static void check(boolean cond, String name) {26 if (!cond) throw new AssertionError("FAILED: " + name);27 System.out.println(" PASS " + name);28 }29}