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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int minCostClimbingStairs(int* cost, int costSize) {
5 int *dp = (int*)malloc((costSize + 1) * sizeof(int));
6 dp[0] = cost[0];
7 dp[1] = cost[1];
8 for (int i = 2; i < costSize; i++) {
9 dp[i] = (dp[i-1] < dp[i-2] ? dp[i-1] : dp[i-2]) + cost[i];
10 }
11 int result = dp[costSize-1] < dp[costSize-2] ? dp[costSize-1] : dp[costSize-2];
12 free(dp);
13 return result;
14}This solution initializes a dynamic programming array to handle the cost calculations. It then iterates through the cost array, updating the dp array with the minimum cost to reach each step by considering the costs of the previous two steps. The result is the minimum of the values from the last two steps, representing the total minimum cost to reach the top.
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)
1#include <stdio.h>
2
3int minCostClimbingStairs(int* cost, int costSize) {
4 int prev = cost[0];
5 int curr = cost[1];
6 for (int i = 2; i < costSize; i++) {
7 int next = (prev < curr ? prev : curr) + cost[i];
8 prev = curr;
9 curr = next;
10 }
11 return (prev < curr ? prev : curr);
12}This C solution reduces space by using two variables, prev and curr, to store the two previous minimum costs. As it iterates through the cost array, it updates these variables based on their minimum and the current cost. Finally, it returns the minimum of the last two values stored in prev and curr.