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¶
"""
- 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;
}
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