This approach uses a dynamic programming table to store the minimum cost at each step. The key idea is that to reach step i, you can come from step i-1 or step i-2, and you need to pay the cost associated with landing on step i. Thus, the cost to reach step i is the minimum of the cost to reach steps i-1 or i-2 plus cost[i]. The solution returns the minimum cost to reach the top from the last two steps.
Time Complexity: O(n), where n is the number of steps as we traverse the list once.
Space Complexity: O(n), as we need an additional array to store minimum costs at each step.
1class Solution {
2 public int minCostClimbingStairs(int[] cost) {
3 int n = cost.length;
4 int[] dp = new int[n + 1];
5 dp[0] = cost[0];
6 dp[1] = cost[1];
7 for (int i = 2; i < n; i++) {
8 dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
9 }
10 return Math.min(dp[n - 1], dp[n - 2]);
11 }
12}This approach uses an integer array dp to store the minimum cost up to each step. It begins from step 0 and performs a loop to fill dp by considering the cost from the previous two steps, until it reaches the top of the stairs. The solution then calculates the minimum between the last two steps to get the final result.
This approach optimizes the space usage of the dynamic programming solution by only retaining two variables to store the minimal costs for the last two steps, instead of an entire table. This is possible because each step's cost only depends on the previous two calculations. You update these two variables iteratively to find the minimum cost to reach the top.
Time Complexity: O(n)
Space Complexity: O(1)
1class Solution {
2 public int minCostClimbingStairs(int[] cost) {
3 int prev = cost[0];
4 int curr = cost[1];
5 for (int i = 2; i < cost.length; i++) {
6 int next = Math.min(prev, curr) + cost[i];
7 prev = curr;
8 curr = next;
9 }
10 return Math.min(prev, curr);
11 }
12}By storing only two integer values prev and curr, the Java solution efficiently computes the minimum cost. These two values are updated iteratively to track minimized costs. Resulting in a space-optimized solution that provides the desired result by returning the lesser of the two values after completing all calculations.