Advanced Dynamic Programming

0/1 Knapsack

For each item, decide to take or skip it. dp[w] tracks the best value achievable with capacity w; iterate weight backward so each item is used at most once.

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for wt, val in zip(weights, values):
        for w in range(capacity, wt - 1, -1):
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[capacity]

Output:

knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)  # 9

Longest Common Subsequence

dp[i][j] is the LCS length of text1[:i] and text2[:j]. Matching characters extend the diagonal; otherwise take the best of skipping one character from either string.

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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[m][n]

Output:

lcs('abcde', 'ace')  # 3 ('ace')

Longest Increasing Subsequence

The O(n^2) version tries every previous index. A faster O(n log n) version keeps a tails array of the smallest tail for each subsequence length, using binary search to place each new number.

import bisect

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

Output:

length_of_lis([10, 9, 2, 5, 3, 7, 101, 18])  # 4  ([2,3,7,101] etc.)

Recognize the shape

Two strings/sequences and a comparison → LCS-style 2D DP. A single sequence with 'increasing/decreasing' → LIS-style. A set of items with a capacity limit → knapsack-style.