Knapsack and LIS in Python: Two DP Patterns Explained

Most dynamic programming questions fall into a handful of families, and two of them cover a surprising amount of interview ground. Knapsack asks, for each item, take it or leave it? and lives on a budget axis. Longest Increasing Subsequence asks, for each position, how long a chain can end here? and lives on an order axis. Once you can tell which question a problem is asking, the state, the loop and the base case almost write themselves.

This guide covers both side by side, including the two mistakes that return plausible-looking wrong answers instead of crashing. If DP is still new, start with dynamic programming for beginners. All code below was run, and both algorithms were compared with brute force: 2,000 random knapsack instances and 3,000 random sequences.

Two patterns, two questions

0/1 Knapsack

You have items with a weight and a value, a bag with a fixed capacity, and each item may be used once. Maximise the total value. A 2D table dp[i][c] (best value using the first i items with capacity c) works, but row i only ever reads row i − 1, so one array is enough.

def knap_1d(weights, values, cap):
    dp = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):      # capacity goes DOWNWARDS
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]

knap_1d([1, 3, 4, 5], [1, 4, 5, 7], 7)   # -> 9   (the items of weight 3 and 4)

Read the inner line as: either keep the best value I already had for capacity c (skip the item), or take the item and add its value to the best I could do with the remaining c - w. The 2D version and the 1D version gave the same answer, 9, and matched a brute force over every subset on 2,000 random inputs.

The loop direction that silently gives wrong answers

Iterating capacity upwards looks equivalent, and it even gets the sample above right. But when you go upwards, dp[c - w] has already been updated for the same item, so the item can be taken again and again. That is the unbounded knapsack, a different problem. One item of weight 2 and value 10 in a bag of capacity 6 shows it:

correct (downwards): 10
forward  (upwards):   30    # the single item was used three times

Downward means “read only values from before this item”, which is exactly the meaning of 0/1. Upward is the right choice only when items can repeat, as in Coin Change.

Subset-sum problems in a knapsack costume

Partition Equal Subset Sum

Can an array be split into two halves with equal sums? If the total is odd the answer is no. Otherwise ask whether some subset reaches exactly half. That is knapsack with weight equal to value and a yes/no table.

def can_partition(nums):
    s = sum(nums)
    if s % 2:
        return False
    t = s // 2
    dp = [True] + [False] * t
    for x in nums:
        for c in range(t, x - 1, -1):
            dp[c] = dp[c] or dp[c - x]
    return dp[t]

can_partition([1, 5, 11, 5])   # -> True   (11 and 1 + 5 + 5)
can_partition([1, 2, 3, 5])    # -> False

Python offers a neat shortcut: keep the reachable sums as the bits of one integer, and shifting by x adds x to every reachable sum at once.

def can_partition_bits(nums):
    s = sum(nums)
    if s % 2:
        return False
    t = s // 2
    bits = 1
    for x in nums:
        bits |= bits << x
    return bool(bits >> t & 1)

It returned the same answers on both examples. It is a nice thing to mention after the standard solution, not instead of it.

Target Sum

Assign + or − to each number so the result equals the target. Call the positive group P and the negative group N. Then P − N = target and P + N = total, so P = (total + target) / 2. The problem becomes: in how many ways can a subset sum to P? Same loop, but counting instead of max.

def target_sum(nums, target):
    s = sum(nums)
    if abs(target) > s or (s + target) % 2:
        return 0
    t = (s + target) // 2
    dp = [1] + [0] * t
    for x in nums:
        for c in range(t, x - 1, -1):
            dp[c] += dp[c - x]
    return dp[t]

target_sum([1, 1, 1, 1, 1], 3)   # -> 5
target_sum([1], 1)               # -> 1

Compare that with the pure brute force in the backtracking guide: the same choices, but the table collapses the repeated work.

Longest Increasing Subsequence

Given an array, find the length of the longest strictly increasing subsequence (not necessarily contiguous). The direct DP has dp[i] as the longest chain ending exactly at index i, extended from any earlier smaller value.

def lis_n2(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

That is O(n²), which is fine for a few thousand elements. For more, there is a classic O(n log n) idea: maintain tails, where tails[k] is the smallest possible last value of any increasing subsequence of length k + 1. That array is always sorted, so each new number finds its slot with binary search. Either it extends the longest chain, or it replaces a larger tail and makes future extension easier.

import bisect

def lis_fast(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)

The trace for [10, 9, 2, 5, 3, 7, 101, 18] shows what tails holds after each number:

10   -> [10]
9    -> [9]
2    -> [2]
5    -> [2, 5]
3    -> [2, 3]
7    -> [2, 3, 7]
101  -> [2, 3, 7, 101]
18   -> [2, 3, 7, 18]      # length 4 is the answer

Be careful not to read tails as the subsequence itself. At the end it is [2, 3, 7, 18], but 3 comes after 5 in the array, so that exact chain does not exist. Only the length is guaranteed. To print an actual subsequence, use the O(n²) version with a predecessor array. For this input it produces [2, 5, 7, 101]. The tails trick is greedy at heart, in the spirit of the greedy algorithms guide.

The wrong bisect gives the wrong problem

Swap bisect_left for bisect_right and the code stops requiring strictly increasing values. It counts non-decreasing chains instead. On [7, 7, 7, 7] the three versions printed:

lis_n2([7,7,7,7])          -> 1
lis_fast (bisect_left)     -> 1
lis_fast (bisect_right)    -> 4     # longest NON-decreasing subsequence

That behaviour is useful when a problem allows equal values: with bisect_right, the array [1, 3, 2, 2, 4] gives 4. The rule is simple. Strict means bisect_left, non-strict means bisect_right. If bisect itself feels shaky, revisit the binary search templates.

Russian Doll Envelopes

An envelope fits in another only if both width and height are strictly smaller. Sort by width ascending, and for equal widths sort height descending, so two envelopes of the same width can never be chained. Then the answer is the LIS of the heights.

def max_envelopes(env):
    env.sort(key=lambda e: (e[0], -e[1]))
    return lis_fast([h for _, h in env])

max_envelopes([[5, 4], [6, 4], [6, 7], [2, 3]])   # -> 3

How to recognise which pattern you are in

• A budget that items consume (weight, sum, count) and each item is used once: knapsack, with the budget as the array index.
• An ordering constraint over a sequence (increasing, nested, chained): LIS or one of its disguises.
• Items may repeat: loop the budget upwards. Items are single-use: loop it downwards.
• Counting ways instead of maximising: replace max with += and start from dp[0] = 1.

Complexity summary

Knapsack and its subset-sum cousins cost O(n · capacity) time and O(capacity) space. LIS costs O(n²) time with O(n) space, or O(n log n) with the tails array. Note that O(n · capacity) is pseudo-polynomial: it depends on the numeric value of the capacity, not just the input length. For the formal vocabulary, see Big O notation explained, and for the helpers used here, the Python cheat sheet. A sensible practice order is Partition Equal Subset Sum, Target Sum, Longest Increasing Subsequence, then Russian Doll Envelopes.