Min Cost Climbing Stairs
Problem Description
You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
Example 1:
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.The total cost is 6.
Constraints:
2 <= cost.length <= 10000 <= cost[i] <= 999
Solve it on LeetCode
Approaches
1. Recursion
Intuition:
Start by identifying that you can reach step i from either step i-1 or i-2. This gives rise to a recursive relation where the cost to reach the i-th step is the cost of the step itself plus the minimum of the costs to reach the two preceding steps.
Code:
- Time Complexity: O(2^n) - The function calculates each step repeatedly.
- Space Complexity: O(n) - Due to stack space used in recursion.
2. Top-Down Dynamic Programming (Memoization)
Intuition:
To optimize the recursive solution, we can store the results of subproblems (i.e., costs for each step) and reuse them instead of solving the same subproblems repeatedly.
Code:
- Time Complexity: O(n) - Each step's cost is computed only once.
- Space Complexity: O(n) - Due to place for memoization.
3. Bottom-Up Dynamic Programming
Intuition:
Iteratively build up the solution from the base cases (steps 0 and 1) to the target steps, avoiding recursion overhead.
Code:
- Time Complexity: O(n) - We only iterate through the array once.
- Space Complexity: O(n) - To store minimal costs for each step.
4. Optimized Bottom-Up Approach
Intuition:
Instead of maintaining an array for dynamic programming, we only need to keep track of the last two costs since the cost to reach each step depends only on the two preceding steps.
Code:
- Time Complexity: O(n) - Only a single pass through the input is needed.
- Space Complexity: O(1) - Use only a fixed amount of extra space, independent of input size.