Leetcode 70 climb stairs dp
int climbStairs(int n) {
Problem Statement
if (n <= 1) return 1;
You are climbing a staircase with n steps. Each time, you can climb
either 1 or 2 steps. In how many distinct ways can you climb to the int prev1 = 1, prev2 = 1;
top? for (int i = 2; i <= n; ++i) {
Example: int curr = prev1 + prev2;
prev2 = prev1;
Input: n = 2
Output: 2 (Ways: [1,1], [2]) prev1 = curr;
Input: n = 3
Output: 3 (Ways: [1,1,1], [1,2], [2,1]) }
return prev1;
Brute Force Approach
}
Idea: Use recursion to explore all possible ways to climb the stairs. At
Python
each step, you can either take 1 step or 2 steps, and you recursively
calculate the number of ways for the remaining steps. def climbStairs(n: int) -> int:
Steps: if n == 0:
return 1
1. Define a recursive function climb(n) that returns the number of
ways to climb n steps. if n < 0:
2. Base cases:
o If n == 0, you’ve reached the top, so return 1 (one valid
return 0
way). return climbStairs(n - 1) + climbStairs(n - 2)
o If n < 0, you’ve overshot the stairs, so return 0 (invalid
way).
3. For each step, recursively compute:
o Ways to climb n-1 steps (if you take 1 step).
o Ways to climb n-2 steps (if you take 2 steps). def climbStairs(n: int) -> int:
4. Sum the results of the two recursive calls.
if n <= 1:
Time Complexity: O(2^n), as each call branches into two more calls, return 1
forming a binary tree of depth n. Space Complexity: O(n) for the
recursion stack. prev1, prev2 = 1, 1
for i in range(2, n + 1):
Optimized Approach (Dynamic Programming)
curr = prev1 + prev2
Idea: Use dynamic programming (DP) to store intermediate results
and avoid redundant calculations. This problem resembles the prev2 = prev1
Fibonacci sequence, where the number of ways to climb n steps is the prev1 = curr
sum of ways to climb n-1 and n-2 steps.
return prev1
Steps:
1. Use a DP array (or two variables for space optimization) to
store the number of ways to climb i steps.
2. Initialize:
o dp[0] = 1 (one way to climb 0 steps: do nothing).
o dp[1] = 1 (one way to climb 1 step: take 1 step).
3. For each step i from 2 to n:
o dp[i] = dp[i-1] + dp[i-2], because you can reach step i
by taking 1 step from i-1 or 2 steps from i-2.
4. Return dp[n].
Space-Optimized Version:
Instead of a DP array, use two variables to store only the
previous two values (prev1 for i-1 and prev2 for i-2).
Update these variables in each iteration.
Time Complexity: O(n), as we iterate from 2 to n. Space
Complexity: O(1) for the space-optimized version, O(n) if using a DP
array.
C++
Bruteforce
int climbStairs(int n) {
if (n == 0) return 1;
if (n < 0) return 0;
return climbStairs(n - 1) + climbStairs(n - 2);
}
Leet code 322 coin change if (amount < 0) return INT_MAX;
int minCoins = INT_MAX;
Problem Statement
for (int coin : coins) {
You are given an integer array coins representing coins of different
denominations and an integer amount representing a total amount of int res = coinChange(coins, amount - coin);
money. Return the fewest number of coins needed to make up that if (res != INT_MAX && res >= 0) {
amount. If the amount cannot be made, return -1.
minCoins = min(minCoins, res + 1);
Example:
}
Input: coins = [1,2,5], amount = 11 }
Output: 3 (Explanation: 11 = 5 + 5 + 1)
Input: coins = [2], amount = 3 return minCoins == INT_MAX ? -1 : minCoins;
Output: -1 (Explanation: No combination of coins can make 3) }
Constraints: #include <vector>
1 <= coins.length <= 12 using namespace std;
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX);
Brute Force Approach dp[0] = 0;
Idea: Use recursion to try all possible combinations of coins to reach for (int i = 1; i <= amount; ++i) {
the target amount and return the minimum number of coins required. for (int coin : coins) {
Steps: if (coin <= i && dp[i - coin] != INT_MAX) {
dp[i] = min(dp[i], dp[i - coin] + 1);
1. Define a recursive function coinChange(coins, amount) that
returns the minimum number of coins needed. }
2. Base cases:
o If amount == 0, return 0 (no coins needed). }
o If amount < 0, return a large number (e.g., INT_MAX)
}
to indicate an invalid combination.
3. For each coin in coins, recursively: return dp[amount] == INT_MAX ? -1 : dp[amount];
o Subtract the coin value from amount and call
}
coinChange with the remaining amount.
o Add 1 to the result (to account for the current coin). Python
o Take the minimum of all valid recursive calls.
4. If no valid combination is found, return -1. def coinChange(coins: List[int], amount: int) -> int:
if amount == 0:
Time Complexity: O(S^n), where S is the amount and n is the number
of coin denominations, as each recursive call branches into n return 0
subproblems, and the recursion depth can be up to S. Space
Complexity: O(S) for the recursion stack. if amount < 0:
return float('inf')
Optimized Approach (Dynamic Programming)
min_coins = float('inf')
Idea: Use dynamic programming to store the minimum number of for coin in coins:
coins needed for each amount from 0 to the target amount, avoiding
redundant calculations. This is a classic unbounded knapsack problem. res = coinChange(coins, amount - coin)
Steps: if res != float('inf'):
min_coins = min(min_coins, res + 1)
1. Create a DP array dp where dp[i] represents the minimum
number of coins needed to make amount i. return -1 if min_coins == float('inf') else min_coins
2. Initialize:
o dp[0] = 0 (no coins needed for amount 0).
o dp[i] = INT_MAX for all other i from 1 to amount def coinChange(coins: List[int], amount: int) -> int:
(initially assume impossible).
3. For each amount i from 1 to amount: dp = [float('inf')] * (amount + 1)
o For each coin in coins, if coin <= i: dp[0] = 0
Update dp[i] = min(dp[i], dp[i - coin] + 1) if
dp[i - coin] is not INT_MAX. for i in range(1, amount + 1):
4. Return dp[amount] if it’s not INT_MAX; otherwise, return -1.
for coin in coins:
Time Complexity: O(amount * coins.length), as we iterate over each if coin <= i and dp[i - coin] != float('inf'):
amount and each coin. Space Complexity: O(amount) for the DP
array. dp[i] = min(dp[i], dp[i - coin] + 1)
return -1 if dp[amount] == float('inf') else dp[amount]
C++
#include <vector>
using namespace std;
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
