Blind 75 Dynamic Programming Deep Dive

State: ways[i] is the number of ways to reach step i. Recurrence: the last move came from i - 1 or i - 2. Test n = 1, n = 2, and a larger value. The rolling variables store the two previous states.

def climb_stairs(n):
    if n <= 2:
        return n

    two_back = 1
    one_back = 2
    for _ in range(3, n + 1):
        two_back, one_back = one_back, one_back + two_back
    return one_back

State: the best value after considering the prefix ending at the current house. Invariant: prev1 is the best value for the processed prefix and prev2 is the best value before that. The common mistake is adding the current house to a value that may already include the previous house.

def rob(nums):
    prev2 = 0
    prev1 = 0
    for value in nums:
        take = prev2 + value
        skip = prev1
        prev2, prev1 = prev1, max(take, skip)
    return prev1

State: dp[a] is the fewest coins needed for amount a. Base: dp[0] = 0. Impossible states remain larger than any valid answer. Test amount zero, impossible amounts, duplicate coin values, and coin systems where greedy fails.

def coin_change(coins, amount):
    inf = amount + 1
    dp = [inf] * (amount + 1)
    dp[0] = 0

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

    return -1 if dp[amount] == inf else dp[amount]

The O(n^2) DP state is dp[i]: the best increasing subsequence ending at i. The faster O(n log n) approach keeps tails[k], the smallest possible tail for a subsequence of length k + 1. The tails list is not necessarily the final subsequence; it is a compact frontier.

from bisect import bisect_left


def length_of_lis(nums):
    tails = []
    for value in nums:
        i = bisect_left(tails, value)
        if i == len(tails):
            tails.append(value)
        else:
            tails[i] = value
    return len(tails)

State: dp[i] is the number of decodings for the prefix s[:i]. A one-digit transition is valid for 1 through 9; a two-digit transition is valid for 10 through 26. Common mistakes are treating 0 as decodable by itself and forgetting that 30 is invalid.

State: dp[c] is the number of paths to the current row and column c. Each cell can be reached from above or left. A one-dimensional table works because the old dp[c] is the value from above and dp[c - 1] is the value from the left.

def unique_paths(m, n):
    dp = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            dp[c] += dp[c - 1]
    return dp[-1]

State: dp[i][j] is the LCS length between prefixes text1[:i] and text2[:j]. If the final characters match, extend the diagonal answer. Otherwise, drop one final character from either prefix and keep the better answer.

def longest_common_subsequence(text1, text2):
    rows = len(text1) + 1
    cols = len(text2) + 1
    dp = [[0] * cols for _ in range(rows)]

    for i in range(1, rows):
        for j in range(1, cols):
            if text1[i - 1] == text2[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[-1][-1]

State: dp[i] means the prefix s[:i] can be segmented. Prune with the maximum dictionary word length so the inner loop does not inspect impossible cuts on long inputs.

def word_break(s, word_dict):
    words = set(word_dict)
    if not words:
        return s == ""

    max_len = max(len(word) for word in words)
    dp = [False] * (len(s) + 1)
    dp[0] = True

    for i in range(1, len(s) + 1):
        start = max(0, i - max_len)
        for j in range(start, i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[-1]

This is often easier without a DP table. Expand around every odd and even center while the characters match. The invariant is that every expansion step has found one more palindrome with that center. Test empty string, one character, repeated characters, and mixed odd/even palindromes.

Top-down is attractive when the reachable state space is much smaller than the full table, when the recurrence is easier to state recursively, or when you need a fast prototype. Bottom-up is often better when every amount is likely to be reached, recursion depth is risky, or you want predictable memory and iteration order.

Write the state definition next to the table, then trace a tiny input by hand. Check base cases, index offsets, inclusive versus exclusive prefixes, impossible sentinel values, and iteration order. Add one test for each transition path. If memory was optimized, temporarily expand to the full table to verify correctness first.

With a set for dictionary lookup and maximum word length L, the loop considers at most L cuts for each of n positions. Python slicing can copy up to L characters, so the practical bound is closer to O(n * L^2) unless substring views or trie traversal are used. The DP array is O(n), and the dictionary is O(total dictionary text).

Decoding maintains partial hypotheses and scores over time steps. The state includes the prefix, time, model score, language-model score, and sometimes blank or nonblank endings. The staff-level tradeoff is beam width versus latency and memory, with slice-level quality checks for accents, noise, and domain terms.

A simplified offline planning problem can look like knapsack: choose model replicas or optimization work under a GPU budget to maximize quality or traffic covered. In production, queueing, burstiness, rollout risk, and noisy estimates matter, so the DP solution becomes a planning aid rather than the serving policy.