Climbing Stairs
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.dynamic_programming;
import java.util.*;
/
* Problem: Climbing Stairs
* Group: 11. Dynamic Programming
*/
/
* ============================================================================================
* PROBLEM: Climbing Stairs
* ============================================================================================
*
* ---------------------
* 1. Problem Description
* ---------------------
* Given a number of steps A, find the number of distinct ways to reach the top.
* Rules:
* - You can climb 1 step at a time.
* - You can climb 2 steps at a time.
*
* ---------------------
* 2. Logical Breakdown & Mathematical Formulation
* ---------------------
* Let dp[i] be the number of ways to reach step 'i'.
*
* To arrive at step 'i', you could have come from:
* 1. Step 'i-1' (by taking a 1-step jump).
* 2. Step 'i-2' (by taking a 2-step jump).
*
* Recurrence Relation:
* dp[i] = dp[i-1] + dp[i-2]
*
* This is identical to the Fibonacci sequence.
*
* Base Cases:
* - dp[1] = 1 (Way: {1})
* - dp[2] = 2 (Ways: {1,1}, {2})
*
* Optimization:
* Since dp[i] depends only on the previous two states, we don't need an array of size A.
* We can use two variables prev1 and prev2 to achieve O(1) space.
*
* ---------------------
* 3. Constraints & Complexity Analysis
* ---------------------
* Constraints:
* 1 <= A <= 10^5
*
* Time Complexity:
* O(A) - One pass from 1 to A.
*
* Space Complexity:
* O(1) - Using variables instead of an array.
*
* ---------------------
* 4. Input / Output Format
* ---------------------
* Input: Integer A.
* Output: Integer ways.
*
* ============================================================================================
*/
public class ClimbingStairs {
public int solve(int A) {
// TODO: Implement solution
return 0;
}
public int climbStairs(int i) {
return 0;
}
}