Card 1 / 9
Classic DP intro: you're at the bottom of a staircase with n steps. Each move, you can climb 1 or 2 steps. How many distinct ways can you reach the top?
This is Fibonacci in disguise! To reach step n, you came from step n-1 (1 step) or n-2 (2 steps).
n |
result | ways |
|---|---|---|
2 |
2 |
1+1, 2 |
3 |
3 |
1+1+1, 1+2, 2+1 |
5 |
8 |
dp[n] = dp[n-1] + dp[n-2]. Base cases: dp[1] = 1, dp[2] = 2.
// You're climbing a staircase with n steps. Each time you can climb 1 or 2 steps.
// Return the number of distinct ways to reach the top.
int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2;
for (int i = 3; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}Card 2 / 9
Each step has a cost. You can start from step 0 or step 1. Pay cost[i] to move 1 or 2 steps forward. Find the minimum cost to reach the top (past the last step).