DP Matrix Exponentiation Optimized¶
Table of Contents¶
- 70. Climbing Stairs (Easy)
- 509. Fibonacci Number (Easy)
- 1137. N-th Tribonacci Number (Easy)
- 1220. Count Vowels Permutation (Hard)
- 552. Student Attendance Record II (Hard)
- 935. Knight Dialer (Medium)
- 790. Domino and Tromino Tiling (Medium)
- 3337. Total Characters in String After Transformations II (Hard)
- 2851. String Transformation (Hard)
- 2912. Number of Ways to Reach Destination in the Grid (Hard) 👑
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;
}
509. Fibonacci Number¶
"""
- Return the `n-th` Fibonacci number.
- `dp[n]` stores the `n-th` Fibonacci number.
- Formula: `dp[n] = dp[n - 1] + dp[n - 2]`.
- Initialize `dp[0] = 0` and `dp[1] = 1`.
| n | `dp[n-2]` | `dp[n-1]` | `dp[n]` |
| :-: | :-------: | :-------: | :-----: |
| 0 | - | - | 0 |
| 1 | - | 0 | 1 |
| 2 | 0 | 1 | 1 |
| 3 | 1 | 1 | 2 |
| 4 | 1 | 2 | 3 |
| 5 | 2 | 3 | 5 |
| 6 | 3 | 5 | 8 |
| 7 | 5 | 8 | 13 |
| 8 | 8 | 13 | 21 |
| 9 | 13 | 21 | 34 |
| 10 | 21 | 34 | 55 |
"""
from functools import cache
# DP
def fibDP(n: int) -> int:
if n <= 1:
return n
dp = [i for i in range(n + 1)]
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# DP (Optimized)
def fibDPOptimized(n: int) -> int:
if n <= 1:
return n
n1, n2 = 0, 1
for _ in range(2, n + 1):
n1, n2 = n2, n1 + n2
return n2
# Recursive
@cache
def fibRecursive(n: int) -> int:
if n <= 1:
return n
return fibRecursive(n - 1) + fibRecursive(n - 2)
n = 10
print(fibDP(n)) # 55
print(fibDPOptimized(n)) # 55
print(fibRecursive(n)) # 55