Skip to content

DP Matrix Exponentiation Optimized

Table of Contents

70. Climbing Stairs

  • LeetCode | LeetCode CH (Easy)

  • Tags: math, dynamic programming, memoization

  • 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.
n dp[n-2] dp[n-1] dp[n]
0 - - 0
1 - - 1
2 - 1 2
3 1 2 3
4 2 3 5
5 3 5 8
6 5 8 13
7 8 13 21
8 13 21 34
9 21 34 55
10 34 55 89
70. Climbing Stairs - Python Solution
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)


print(climbStairsDP(10))  # 89
print(climbStairsDPOptimized(10))  # 89
print(climbStairsRecursion(10))  # 89
70. Climbing Stairs - C++ Solution
#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() {
    cout << climbStairs(2) << endl;  // 2
    cout << climbStairs(3) << endl;  // 3
    cout << climbStairs(6) << endl;  // 13
    return 0;
}

509. Fibonacci Number

  • LeetCode | LeetCode CH (Easy)

  • Tags: math, dynamic programming, recursion, memoization

  • 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
509. Fibonacci Number - Python Solution
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

1137. N-th Tribonacci Number

1220. Count Vowels Permutation

552. Student Attendance Record II

935. Knight Dialer

790. Domino and Tromino Tiling

3337. Total Characters in String After Transformations II

2851. String Transformation

2912. Number of Ways to Reach Destination in the Grid

Comments