Dynamic Programming, Part 2: The Classic Problems

def coin_change(coins: list[int], amount: int) -> int:
    """Find the minimum number of coins needed to make 'amount'.

    1. STATE:  dp[i] = minimum coins needed to make amount i
    2. RECURRENCE: dp[i] = min(dp[i - coin] + 1) for each coin <= i
       (use one coin of this denomination, then solve for the remainder)
    3. BASE CASE: dp[0] = 0 (0 coins needed to make amount 0)
    4. ORDER: left to right, i from 1 to amount
    5. ANSWER: dp[amount] if < infinity, else -1 (not achievable)

    Time: O(amount * len(coins)), Space: O(amount)
    """
    INF = float("inf")
    dp = [INF] * (amount + 1)
    dp[0] = 0  # base case

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1

    return dp[amount] if dp[amount] != INF else -1

print(coin_change([1, 5, 10, 25], 36))  # 3 (25 + 10 + 1)
print(coin_change([2], 3))              # -1 (impossible with only coin=2)
print(coin_change([1, 2, 5], 11))       # 3 (5 + 5 + 1)

def lcs(s1: str, s2: str) -> int:
    """Find the length of the longest common subsequence.

    A subsequence is a sequence that can be derived from another sequence by
    deleting some (or no) characters without changing the order of the remaining.
    e.g., LCS("ABCBDAB", "BDCAB") = 4 ("BCAB" or "BDAB")

    1. STATE: dp[i][j] = LCS length of s1[:i] and s2[:j]
    2. RECURRENCE:
       if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1  (characters match)
       else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])          (skip one character)
    3. BASE CASES: dp[0][j] = 0, dp[i][0] = 0 (empty string has LCS = 0)
    4. ORDER: row by row, left to right
    5. ANSWER: dp[m][n]

    Time: O(m * n), Space: O(m * n)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

def lcs_with_string(s1: str, s2: str) -> str:
    """Return the actual LCS string by backtracking through the DP table."""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # Backtrack
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            result.append(s1[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(result))

print(lcs("ABCBDAB", "BDCAB"))           # 4
print(lcs_with_string("ABCBDAB", "BDCAB"))  # BDAB
print(lcs("intention", "execution"))     # 5

def knapsack_01(weights: list[int], values: list[int],
                capacity: int) -> int:
    """Classic 0/1 Knapsack: maximize value within weight capacity.
    Each item can be taken at most once (0 or 1 times).

    1. STATE: dp[i][w] = max value using first i items with capacity w
    2. RECURRENCE:
       if weights[i-1] <= w:
           dp[i][w] = max(dp[i-1][w],               # skip item i
                          dp[i-1][w - weights[i-1]] + values[i-1])  # take item i
       else:
           dp[i][w] = dp[i-1][w]                    # item too heavy, must skip
    3. BASE CASES: dp[0][w] = 0 for all w (no items = no value)
    4. ORDER: row by row (outer = items, inner = capacity)
    5. ANSWER: dp[n][capacity]

    Time: O(n * capacity), Space: O(n * capacity)
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Option 1: skip item i
            dp[i][w] = dp[i - 1][w]
            # Option 2: take item i (if it fits)
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]

# 4 items, capacity = 5
weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack_01(weights, values, 5))   # 7 (items 0 and 1: weight 2+3=5, value 3+4=7)
print(knapsack_01(weights, values, 8))   # 10 (items 1 and 3: weight 3+5=8, value 4+6=10)

def lis_dp(nums: list[int]) -> int:
    """Longest Increasing Subsequence. O(n^2) DP approach.

    1. STATE: dp[i] = length of LIS ending at index i
    2. RECURRENCE: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
    3. BASE CASE: dp[i] = 1 for all i (each element is an LIS of length 1)
    4. ORDER: left to right
    5. ANSWER: max(dp)
    """
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n  # base case: every element alone is an LIS of length 1

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:          # nums[j] can extend the sequence
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

import bisect

def lis_binary_search(nums: list[int]) -> int:
    """LIS in O(n log n) using binary search (patience sorting).

    Maintain a 'tails' array: tails[k] = the smallest tail element
    of all increasing subsequences of length k+1.
    """
    tails: list[int] = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)     # extend the longest subsequence
        else:
            tails[pos] = num      # replace to maintain smallest tails
    return len(tails)

seq = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"LIS (O(n^2)):    {lis_dp(seq)}")            # 4 (2,3,7,18 or 2,5,7,18)
print(f"LIS (O(n log n): {lis_binary_search(seq)}")  # 4

def edit_distance(word1: str, word2: str) -> int:
    """Minimum edit operations (insert, delete, replace) to transform word1 → word2.

    Used in: spell checkers, diff tools, DNA alignment, NLP similarity metrics.

    1. STATE: dp[i][j] = min edits to transform word1[:i] into word2[:j]
    2. RECURRENCE:
       if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]  (no operation needed)
       else: dp[i][j] = 1 + min(
           dp[i-1][j],      # delete from word1
           dp[i][j-1],      # insert into word1
           dp[i-1][j-1]     # replace in word1
       )
    3. BASE CASES:
       dp[0][j] = j  (transform empty string to word2[:j] requires j insertions)
       dp[i][0] = i  (transform word1[:i] to empty string requires i deletions)
    4. ORDER: row by row
    5. ANSWER: dp[m][n]

    Time: O(m * n), Space: O(m * n)  [reducible to O(min(m,n)) with rolling row]
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i      # delete all of word1[:i]
    for j in range(n + 1):
        dp[0][j] = j      # insert all of word2[:j]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]   # characters match — free
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete word1[i-1]
                    dp[i][j - 1],      # insert word2[j-1]
                    dp[i - 1][j - 1],  # replace word1[i-1] with word2[j-1]
                )

    return dp[m][n]

print(edit_distance("kitten", "sitting"))   # 3
# kitten → sitten (replace k→s)
# sitten → sittin (replace e→i)
# sittin → sitting (insert g)

print(edit_distance("intention", "execution"))  # 5
print(edit_distance("", "abc"))                 # 3 (insert a, b, c)
print(edit_distance("abc", "abc"))              # 0 (already equal)

import functools

# Same problem, both styles side by side: Coin Change

# --- Top-Down (Memoization) ---
@functools.cache
def coin_change_memo(coins_tuple: tuple[int, ...], amount: int) -> int:
    if amount == 0:
        return 0
    if amount < 0:
        return float("inf")
    return 1 + min(coin_change_memo(coins_tuple, amount - c) for c in coins_tuple)

coins = (1, 5, 10, 25)
result = coin_change_memo(coins, 36)
print(f"Memo result: {result}")  # 3

# --- Bottom-Up (Tabulation) ---
def coin_change_tab(coins: list[int], amount: int) -> int:
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

print(f"Tab result:  {coin_change_tab([1, 5, 10, 25], 36)}")  # 3

# Pattern: left and right pointers move toward each other
def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int] | None:
    """Find two indices that sum to target in a sorted array. O(n)."""
    left, right = 0, len(nums) - 1
    while left < right:
        current = nums[left] + nums[right]
        if current == target:
            return (left, right)
        elif current < target:
            left += 1   # need larger sum
        else:
            right -= 1  # need smaller sum
    return None

print(two_sum_sorted([1, 2, 3, 4, 6], 6))  # (1, 3) -- nums[1]+nums[3] = 2+4 = 6

def is_palindrome(s: str) -> bool:
    """Check if a string is a palindrome. O(n)."""
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1; right -= 1
    return True

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False

# Pattern: slow moves 1 step, fast moves 2 steps
# If there is a cycle, they must eventually meet

def has_cycle(head) -> bool:
    """Detect a cycle in a linked list using Floyd's algorithm. O(n)."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:   # they met — cycle detected
            return True
    return False

def find_duplicate(nums: list[int]) -> int:
    """Find the duplicate number in [1..n] array of length n+1. O(n), O(1) space.

    Treat array values as next-pointers: index 0 → nums[0] → nums[nums[0]] → ...
    The duplicate creates a cycle; cycle entry = duplicate number.
    """
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    # Find entry point of cycle
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

print(find_duplicate([1, 3, 4, 2, 2]))  # 2
print(find_duplicate([3, 1, 3, 4, 2]))  # 3

def longest_substring_no_repeat(s: str) -> int:
    """Length of longest substring without repeating characters. O(n).

    Pattern: expand window right by advancing end;
             shrink window left when a repeat is found.
    """
    char_index: dict[str, int] = {}
    start = 0
    max_len = 0

    for end, char in enumerate(s):
        if char in char_index and char_index[char] >= start:
            start = char_index[char] + 1  # shrink: move start past the repeat
        char_index[char] = end
        max_len = max(max_len, end - start + 1)

    return max_len

print(longest_substring_no_repeat("abcabcbb"))  # 3 ("abc")
print(longest_substring_no_repeat("bbbbb"))     # 1 ("b")
print(longest_substring_no_repeat("pwwkew"))    # 3 ("wke")
print(longest_substring_no_repeat("abba"))      # 2 ("ba") -- see the question below

def max_sum_subarray_k(nums: list[int], k: int) -> int:
    """Maximum sum of any subarray of size k. O(n).

    Fixed-size sliding window: add the new element on the right,
    remove the old element on the left.
    """
    window_sum = sum(nums[:k])
    max_sum = window_sum

    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]   # slide the window
        max_sum = max(max_sum, window_sum)

    return max_sum

print(max_sum_subarray_k([2, 1, 5, 1, 3, 2], k=3))  # 9 (subarray [5,1,3])