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¶
from functools import cache
class Solution:
def climbStairs(self, n: int) -> int:
"""Optimized DP: O(n) time, O(1) space.
Only the previous two counts are needed to compute the next stair.
"""
if n <= 2:
return n
first, second = 1, 2
for _ in range(3, n + 1):
first, second = second, first + second
return second
def climbStairsDP(self, n: int) -> int:
"""Tabulation DP: O(n) time, O(n) space.
Each stair count is the sum of the ways to reach the previous two stairs.
"""
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
def climbStairsGreedy(self, n: int) -> int:
"""Greedy Rolling Counts: O(n) time, O(1) space.
The next answer is always determined by the two latest reachable counts.
"""
if n <= 2:
return n
prev, cur = 1, 2
for _ in range(3, n + 1):
prev, cur = cur, prev + cur
return cur
def climbStairsDFS(self, n: int) -> int:
"""Memoized DFS: O(n) time, O(n) space.
Caching prevents recomputing the same remaining-stair subproblems.
"""
@cache
def dfs(i: int) -> int:
if i <= 2:
return i
return dfs(i - 1) + dfs(i - 2)
return dfs(n)
def test_climb_stairs():
s = Solution()
for fn in (
s.climbStairs,
s.climbStairsDP,
s.climbStairsGreedy,
s.climbStairsDFS,
):
assert fn(1) == 1
assert fn(2) == 2
assert fn(3) == 3
assert fn(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
2466. Count Ways To Build Good Strings¶
from functools import cache
class Solution:
def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
"""Top-Down DP: O(high) time, O(high) space.
Count strings by final length after appending zero-sized
or one-sized blocks.
"""
MOD = 1_000_000_007
@cache
def dfs(i):
if i < 0:
return 0
if i == 0:
return 1
return (dfs(i - zero) + dfs(i - one)) % MOD
return sum(dfs(i) for i in range(low, high + 1)) % MOD
def test_count_good_strings():
s = Solution()
assert s.countGoodStrings(3, 3, 1, 1) == 8
assert s.countGoodStrings(2, 3, 1, 2) == 5
assert s.countGoodStrings(1, 1, 1, 2) == 1