Skip to content

DP Climbing Stairs

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

746. Min Cost Climbing Stairs

  • LeetCode | LeetCode CH (Easy)

  • Tags: array, dynamic programming

  • Return the minimum cost to reach the top of the stairs.

  • dp[n] stores the minimum cost 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
746. Min Cost Climbing Stairs - Python Solution
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

377. Combination Sum IV - Python Solution
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

2266. Count Number of Texts

2533. Number of Good Binary Strings

Comments