Watch 8 video solutions for Climbing Stairs II, a medium level problem involving Array, Dynamic Programming. This walkthrough by Sanyam IIT Guwahati has 636 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are climbing a staircase with n + 1 steps, numbered from 0 to n.
You are also given a 1-indexed integer array costs of length n, where costs[i] is the cost of step i.
From step i, you can jump only to step i + 1, i + 2, or i + 3. The cost of jumping from step i to step j is defined as: costs[j] + (j - i)2
You start from step 0 with cost = 0.
Return the minimum total cost to reach step n.
Example 1:
Input: n = 4, costs = [1,2,3,4]
Output: 13
Explanation:
One optimal path is 0 → 1 → 2 → 4
| Jump | Cost Calculation | Cost |
|---|---|---|
| 0 → 1 | costs[1] + (1 - 0)2 = 1 + 1 |
2 |
| 1 → 2 | costs[2] + (2 - 1)2 = 2 + 1 |
3 |
| 2 → 4 | costs[4] + (4 - 2)2 = 4 + 4 |
8 |
Thus, the minimum total cost is 2 + 3 + 8 = 13
Example 2:
Input: n = 4, costs = [5,1,6,2]
Output: 11
Explanation:
One optimal path is 0 → 2 → 4
| Jump | Cost Calculation | Cost |
|---|---|---|
| 0 → 2 | costs[2] + (2 - 0)2 = 1 + 4 |
5 |
| 2 → 4 | costs[4] + (4 - 2)2 = 2 + 4 |
6 |
Thus, the minimum total cost is 5 + 6 = 11
Example 3:
Input: n = 3, costs = [9,8,3]
Output: 12
Explanation:
The optimal path is 0 → 3 with total cost = costs[3] + (3 - 0)2 = 3 + 9 = 12
Constraints:
1 <= n == costs.length <= 105āāāāāāā1 <= costs[i] <= 104Problem Overview: You are given a staircase where each index represents a step and the value at that index indicates how many steps you can climb forward from there. The goal is to compute how many distinct ways you can reach the final step starting from the beginning.
Approach 1: Recursive Exploration (Exponential Time)
The most direct idea is to try every possible jump from the current step. From index i, iterate through all reachable steps from i + 1 up to i + nums[i]. Recursively compute the number of ways to reach the top from each of those positions and sum the results. This approach mirrors the decision tree of the problem but recomputes the same subproblems many times. Time complexity grows exponentially O(k^n) in the worst case, with O(n) recursion stack space.
Approach 2: Dynamic Programming with Memoization (O(n * k) time, O(n) space)
Dynamic Programming removes repeated work by caching results for each step. Define dp[i] as the number of ways to reach the end starting from step i. When computing dp[i], iterate over all reachable next steps and sum their values: dp[i] += dp[j] for j in the range (i+1 ... i+nums[i]). Memoization ensures each state is solved once. The total work becomes proportional to the number of states multiplied by the maximum jump length, giving O(n * k) time and O(n) space.
Approach 3: Bottom-Up Dynamic Programming (O(n * k) time, O(n) space)
The same recurrence can be computed iteratively. Start from the last step, where there is exactly one way to finish. Move backward through the array and compute dp[i] by summing values of reachable future states. Each step performs a bounded loop over its jump range, making the total complexity O(n * k). This approach avoids recursion overhead and is usually preferred in production implementations. It relies heavily on the idea that every state depends only on states ahead of it.
Both optimized solutions rely on recognizing overlapping subproblems, which is the core signal for Dynamic Programming. The iteration over the input also highlights its relationship with Array traversal problems and typical state transition patterns.
Recommended for interviews: Bottom-up Dynamic Programming. Interviewers expect you to first recognize the recursive structure and then convert it into a DP relation. Mentioning the brute force recursion shows you understand the search space, but implementing the O(n * k) DP solution demonstrates control over state design and optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Brute Force | O(k^n) | O(n) | Conceptual understanding of the search space or very small inputs |
| DP with Memoization | O(n * k) | O(n) | Top-down reasoning when recursion feels more natural |
| Bottom-Up Dynamic Programming | O(n * k) | O(n) | Preferred production or interview solution due to iterative efficiency |