Skip to content

1D Dynamic Programming

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

198. House Robber

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, dynamic programming

  • Return the maximum amount of money that can be robbed from the houses. No two adjacent houses can be robbed.

  • dp[n] stores the maximum amount of money that can be robbed from the first n houses.

  • Formula: dp[n] = max(dp[n - 1], dp[n - 2] + nums[n]).
    • Skip: dp[n] → dp[n - 1]
    • Rob: dp[n] → dp[n - 2] + nums[n]
  • Initialize dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]).
  • Return dp[-1].
  • Example: nums = [2, 7, 9, 3, 1]
n nums[n] dp[n-2] dp[n-1] dp[n-2] + nums[n] dp[n]
0 2 - 2 - 2
1 7 - 7 - 7
2 9 2 7 11 11
3 3 7 11 10 11
4 1 11 11 12 12
198. House Robber - Python Solution
from typing import List


# DP (House Robber)
def rob1(nums: List[int]) -> int:
    if len(nums) < 3:
        return max(nums)

    dp = [0 for _ in range(len(nums))]
    dp[0], dp[1] = nums[0], max(nums[0], nums[1])

    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[-1]


# DP (House Robber) Optimized
def rob2(nums: List[int]) -> int:
    f0, f1 = 0, 0

    for num in nums:
        f0, f1 = f1, max(f1, f0 + num)

    return f1


nums = [2, 7, 9, 3, 1]
print(rob1(nums))  # 12
print(rob2(nums))  # 12
198. House Robber - C++ Solution
#include <iostream>
#include <vector>
using namespace std;

int rob(vector<int> &nums) {
    int prev = 0, cur = 0, temp = 0;

    for (int num : nums) {
        temp = cur;
        cur = max(cur, prev + num);
        prev = temp;
    }
    return cur;
}

int main() {
    vector<int> nums = {2, 7, 9, 3, 1};
    cout << rob(nums) << endl;  // 12
    return 0;
}

139. Word Break

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, hash table, string, dynamic programming, trie, memoization

139. Word Break - Python Solution
from typing import List


# DP (Unbounded Knapsack)
def wordBreak(s: str, wordDict: List[str]) -> bool:
    n = len(s)
    dp = [False for _ in range(n + 1)]
    dp[0] = True

    for i in range(1, n + 1):
        for word in wordDict:
            m = len(word)
            if s[i - m : i] == word and dp[i - m]:
                dp[i] = True
    return dp[-1]


s = "leetcode"
wordDict = ["leet", "code"]
print(wordBreak(s, wordDict))  # True

322. Coin Change

322. Coin Change - Python Solution
from typing import List


def coinChange(coins: List[int], amount: int) -> int:
    dp = [float("inf") for _ in range(amount + 1)]

    dp[0] = 0

    for i in range(1, amount + 1):
        for c in coins:
            if i - c >= 0:
                dp[i] = min(dp[i], 1 + dp[i - c])

    return dp[amount] if dp[amount] != float("inf") else -1


coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount))  # 3

300. Longest Increasing Subsequence

300. Longest Increasing Subsequence - Python Solution
from functools import cache
from typing import List


# DP - LIS
def lengthOfLISMemo(nums: List[int]) -> int:
    n = len(nums)
    if n <= 1:
        return n

    @cache
    def dfs(i: int) -> int:
        res = 0
        for j in range(i):
            if nums[j] < nums[i]:
                res = max(res, dfs(j))
        return res + 1

    return max(dfs(i) for i in range(n))


# DP - LIS
def lengthOfLISTable(nums: List[int]) -> int:
    n = len(nums)
    if n <= 1:
        return n

    dp = [1 for _ in range(n)]

    for i in range(n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)


if __name__ == "__main__":
    assert lengthOfLISMemo([10, 9, 2, 5, 3, 7, 101, 18]) == 4
    assert lengthOfLISTable([10, 9, 2, 5, 3, 7, 101, 18]) == 4
    assert lengthOfLISMemo([0, 1, 0, 3, 2, 3]) == 4
    assert lengthOfLISTable([0, 1, 0, 3, 2, 3]) == 4
    assert lengthOfLISMemo([7, 7, 7, 7]) == 1
    assert lengthOfLISTable([7, 7, 7, 7]) == 1

Comments