Reference: LeetCode
Difficulty: Easy

My Post: Java Solutions Recurrence, DP Bottom-up (easy-understand with comments)

Problem

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Note:

  1. cost will have a length in the range [2, 1000].
  2. Every cost[i] will be an integer in the range [0, 999].

Example: 

1
2
3
4
5
6
7
8
9
10
11
12
// notice the top is at stair n (not the last element)
Input: cost = [10, 15, 20]
Output: 15

Input: cost = [0, 0, 0, 0]
Output: 0

Input: cost = [0, 1, 2, 0]
Output: 1

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6

Analysis

Recursion

Check out the comment.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// the top stair is at position n, not the last element at (n - 1)
// If n == 0 or n == 1, the cost is 0 because we can reach the top without cost.
// Define: opt(i) is minimum cost to reach step i; opt(n) is our solution.
// Recurrence: opt(i) = min{ opt(i - 2) + cost[i - 2], opt(i - 1) + cost[i - 1] }
// Initialization: opt(0) = 0, opt(1) = 0 (two starting points)
// Caveat: when i == 1, no need to consider starting from 0 -> 1, since cost[0] + cost[1] must be greater than cost[1] only.
public int minCostClimbingStairs(int[] cost) {
  int n = cost.length;
  // if (n == 0 || n == 1) return 0; // this check is unnecessary, consider why?
  return minCost(n, cost); // i = 0...n
}

private int minCost(int i, int[] cost) {
  if (i == 0 || i == 1) { // base case: two starting points
    return 0; // notice: 0 instead of cost[i], consider why? The cost is added in the recurrence
  }
  int f1 = minCost(i - 2, cost) + cost[i - 2];
  int f2 = minCost(i - 1, cost) + cost[i - 1];
  return Math.min(f1, f2);
}

Time: $O(2^N)$
Space: $O(N)$

DP (bottom-up)

1
2
3
4
5
6
7
8
9
10
public int minCostClimbingStairs(int[] cost) {
  int n = cost.length;
  int[] opt = new int[n + 1];
  opt[0] = 0; // init
  opt[1] = 0;
  for (int i = 2; i <= n; ++i) {
    opt[i] = Math.min(opt[i - 1] + cost[i - 1], opt[i - 2] + cost[i - 2]);
  }
  return opt[n];
}

Time: $O(N)$
Space: $O(N)$

Optimized Space Complexity:

Note: f1 is corresponding with cost[i - 2]!

1
2
3
4
5
6
7
8
9
10
public int minCostClimbingStairs(int[] cost) {
  int n = cost.length;
  int f1 = 0, f2 = 0; // init
  for (int i = 2; i <= n; ++i) {
    int temp = Math.min(f1 + cost[i - 2], f2 + cost[i - 1]); // [i - 2] is before
    f1 = f2;
    f2 = temp;
  }
  return f2;
}

Time: $O(N)$
Space: $O(1)$