DP Climbing Stairs¶
Table of Contents¶
- 70. Climbing Stairs (Easy)
- 746. Min Cost Climbing Stairs (Easy)
- 377. Combination Sum IV (Medium)
- 2466. Count Ways To Build Good Strings (Medium)
- 2266. Count Number of Texts (Medium)
- 2533. Number of Good Binary Strings (Medium) 👑
70. Climbing Stairs¶
"""
- Return the number of distinct ways to reach the top of the stairs.
- `dp[n]` stores the number of distinct ways to reach the `n-th` stair.
- Formula: `dp[n] = dp[n - 1] + dp[n - 2]`.
- Initialize `dp[0] = 0`, `dp[1] = 1`, and `dp[2] = 2`.
"""
from functools import cache
# DP
def climbStairsDP(n: int) -> int:
if n <= 2:
return n
dp = [i for i in range(n + 1)]
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# DP (Optimized)
def climbStairsDPOptimized(n: int) -> int:
if n <= 2:
return n
first, second = 1, 2
for _ in range(3, n + 1):
first, second = second, first + second
return second
# Recursion
def climbStairsRecursion(n: int) -> int:
@cache
def dfs(i: int) -> int:
if i <= 1:
return 1
return dfs(i - 1) + dfs(i - 2)
return dfs(n)
# Greedy
def climbStairsGreedy(n: int) -> int:
if n <= 2:
return n
p1, p2 = 1, 2
for _ in range(3, n + 1):
p1, p2 = p2, p1 + p2
return p2
if __name__ == "__main__":
assert climbStairsDP(10) == 89
assert climbStairsDPOptimized(10) == 89
assert climbStairsRecursion(10) == 89
assert climbStairsGreedy(10) == 89
#include <cassert>
#include <iostream>
using namespace std;
int climbStairs(int n) {
if (n <= 2) return n;
int f1 = 1, f2 = 2;
int res;
int i = 3;
while (i <= n) {
res = f1 + f2;
f1 = f2;
f2 = res;
i++;
}
return res;
}
int main() {
assert(climbStairs(2) == 2);
assert(climbStairs(5) == 8);
assert(climbStairs(10) == 89);
return 0;
}
746. Min Cost Climbing Stairs¶
"""
- Return the minimum cost to reach the top of the stairs.
- `dp[n]` stores the <u>minimum cost</u> to reach the `n-th` stair.
- Formula: `dp[n] = cost[n] + min(dp[n - 1], dp[n - 2])`.
- Initialize `dp[0] = cost[0]` and `dp[1] = cost[1]`.
- Return `min(dp[-1], dp[-2])`.
- Example: `cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]`
| n | `cost[n]` | `dp[n-2]` | `dp[n-1]` | `dp[n]` |
| :-: | :-------: | :-------: | :-------: | :-----: |
| 0 | 1 | - | - | 1 |
| 1 | 100 | - | 1 | 100 |
| 2 | 1 | 1 | 100 | 2 |
| 3 | 1 | 100 | 2 | 3 |
| 4 | 1 | 2 | 3 | 3 |
| 5 | 100 | 3 | 3 | 103 |
| 6 | 1 | 3 | 103 | 4 |
| 7 | 1 | 103 | 4 | 5 |
| 8 | 100 | 4 | 5 | 104 |
| 9 | 1 | 5 | 104 | 6 |
"""
from typing import List
def minCostClimbingStairs(cost: List[int]) -> int:
dp = [0 for _ in range(len(cost))]
dp[0], dp[1] = cost[0], cost[1]
for i in range(2, len(cost)):
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
print(dp)
return min(dp[-1], dp[-2])
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
print(minCostClimbingStairs(cost)) # 6
377. Combination Sum IV¶
from typing import List
def combinationSum4(nums: List[int], target: int) -> int:
dp = [0 for _ in range(target + 1)]
dp[0] = 1
for i in range(1, target + 1):
for j in range(len(nums)):
if i - nums[j] >= 0:
dp[i] += dp[i - nums[j]]
return dp[target]
nums = [1, 2, 3]
target = 4
print(combinationSum4(nums, target)) # 7