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

118. Pascal's Triangle¶

LeetCode | LeetCode CH (Easy)
Tags: array, dynamic programming
Generate the first numRows of Pascal's triangle.

                 numRows    index
     1              1         0
    1 1             2         1
   1 2 1            3         2
  1 3 3 1           4         3
 1 4 6 4 1          5         4

118. Pascal's Triangle - Python Solution

from typing import List


def generate(numRows: int) -> List[List[int]]:
    dp = [[1] * i for i in range(1, numRows + 1)]

    if numRows <= 2:
        return dp

    for i in range(2, numRows):
        for j in range(1, i):
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

    return dp


print(generate(numRows=5))
#     [[1],
#    [1, 1],
#   [1, 2, 1],
#  [1, 3, 3, 1],
# [1, 4, 6, 4, 1]]

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

279. Perfect Squares¶

LeetCode | LeetCode CH (Medium)
Tags: math, dynamic programming, breadth first search

279. Perfect Squares - Python Solution

import math


# DP - Knapsack Unbounded
def numSquares(n: int) -> int:
    dp = [float("inf") for _ in range(n + 1)]
    dp[0] = 0

    for i in range(1, n + 1):
        for j in range(1, int(math.sqrt(n)) + 1):
            dp[i] = min(dp[i], dp[i - j**2] + 1)

    return dp[n]


n = 12
print(numSquares(n))  # 3

322. Coin Change¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming, breadth first search

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

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

300. Longest Increasing Subsequence¶

LeetCode | LeetCode CH (Medium)
Tags: array, binary search, dynamic programming

300. Longest Increasing Subsequence - Python Solution

from typing import List


# DP - LIS
def lengthOfLIS(nums: List[int]) -> int:
    # TC: O(n^2)
    # SC: O(n)
    n = len(nums)
    if n <= 1:
        return n

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

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

    return max(dp)


nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lengthOfLIS(nums))  # 4

152. Maximum Product Subarray¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming

152. Maximum Product Subarray - Python Solution

from typing import List


# DP - Kadane
def maxProduct(nums: List[int]) -> int:
    n = len(nums)
    dp_max = [0 for _ in range(n)]
    dp_min = [0 for _ in range(n)]

    dp_max[0] = nums[0]
    dp_min[0] = nums[0]
    max_product = nums[0]

    for i in range(1, n):
        dp_max[i] = max(
            nums[i],
            nums[i] * dp_max[i - 1],
            nums[i] * dp_min[i - 1],
        )
        dp_min[i] = min(
            nums[i],
            nums[i] * dp_max[i - 1],
            nums[i] * dp_min[i - 1],
        )

        max_product = max(max_product, dp_max[i])

    return max_product


nums = [2, 3, -2, 4]
print(maxProduct(nums))  # 6

416. Partition Equal Subset Sum¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming

416. Partition Equal Subset Sum - Python Solution

from functools import cache
from typing import List

from template import knapsack01


# Memoization
def canPartitionMemoization(nums: List[int]) -> bool:
    total = sum(nums)
    n = len(nums)

    if total % 2 == 1 or n <= 1:
        return False

    @cache
    def dfs(i, j):
        if i < 0:
            return j == 0
        return j >= nums[i] and dfs(i - 1, j - nums[i]) or dfs(i - 1, j)

    return dfs(n - 1, total // 2)


# DP - Knapsack 01
def canPartitionTemplate(nums: List[int]) -> bool:
    total = sum(nums)

    if total % 2 == 1 or len(nums) < 2:
        return False

    target = total // 2

    return knapsack01(nums, nums, target) == target


# DP - Knapsack 01
def canPartition(nums: List[int]) -> bool:
    total = sum(nums)

    if total % 2 == 1 or len(nums) < 2:
        return False

    target = total // 2

    dp = [0 for _ in range(target + 1)]

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

    return dp[target] == target


if __name__ == "__main__":
    nums = [1, 5, 11, 5]
    print(canPartitionTemplate(nums))  # True
    print(canPartition(nums))  # True
    print(canPartitionMemoization(nums))  # True

32. Longest Valid Parentheses¶

LeetCode | LeetCode CH (Hard)
Tags: string, dynamic programming, stack

32. Longest Valid Parentheses - Python Solution

# Stack
def longestValidParentheses(s: str) -> int:
    stack = [-1]
    res = 0

    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        elif ch == ")":
            stack.pop()
            if stack:
                res = max(res, i - stack[-1])
            else:
                stack.append(i)

    return res


if __name__ == "__main__":
    print(longestValidParentheses("(()"))  # 2
    print(longestValidParentheses(")()())"))  # 4