Min Cost Climbing Stairs - Solution & Explanation

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.

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.

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.

We design a function dfs(i), which represents the minimum cost required to climb the stairs starting from the i-th step. Therefore, the answer is min(dfs(0), dfs(1)).

The execution process of the function dfs(i) is as follows:

• If i \ge len(cost), it means the current position has exceeded the top of the stairs, and there is no need to climb further, so return 0;
• Otherwise, we can choose to climb 1 step with a cost of cost[i], then recursively call dfs(i + 1); or we can choose to climb 2 steps with a cost of cost[i], then recursively call dfs(i + 2);
• Return the minimum cost between these two options.

To avoid repeated calculations, we use memoization search, saving the results that have already been calculated in an array or hash table.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array cost.

We define f[i] as the minimum cost needed to reach the i-th stair. Initially, f[0] = f[1] = 0, and the answer is f[n].

When i \ge 2, we can reach the i-th stair directly from the (i - 1)-th stair with one step, or from the (i - 2)-th stair with two steps. Therefore, we have the state transition equation:

$ f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2])

The final answer is f[n].

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array cost$.

We notice that the state transition equation for f[i] only depends on f[i - 1] and f[i - 2]. Therefore, we can use two variables f and g to alternately record the values of f[i - 2] and f[i - 1], thus optimizing the space complexity to O(1).