Knapsack DP ·

Table of Contents

Introduction
#

Knapsack DP problems look similar on the surface, but the correct solution depends on three questions:

Can each item be used once or reused many times?
Does dp[...] mean reachable, number of ways, minimum cost, or maximum value?
In 1D compression, should the capacity loop go backward or forward?

Most mistakes come from answering one of these questions incorrectly.

0/1 Knapsack
#

Each item can be used at most once, so the compressed capacity loop goes backward.

from typing import List

def subset_sum(nums: List[int], target: int) -> bool:
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

Backward iteration prevents the current item from being reused in the same item round.

Unbounded Knapsack
#

Each item can be reused, so the capacity loop often goes forward.

from typing import List

def coin_change_min(coins: List[int], amount: int) -> int:
    inf = amount + 1
    dp = [inf] * (amount + 1)
    dp[0] = 0

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

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

Counting Combinations vs Permutations
#

For combinations, put items outside:

for coin in coins:
    for amount forward:
        dp[amount] += dp[amount - coin]

For ordered sequences, put target outside:

for total in range(target + 1):
    for num in nums:
        dp[total] += dp[total - num]

This is the key difference between LC 518 and LC 377.

Grouped / Bounded Knapsack
#

Each group allows at most one option (how many questions of one type, how many coins from one pile, which value one number becomes). Capacity still runs backwards, with the group’s options enumerated inside:

dp = [0] + [inf] * target               # or for counting: [1] + [0] * target
for group in groups:
    for s in range(target, -1, -1):      # backwards: a group is never used twice
        for weight, value in group:      # every option of this group
            if s - weight >= 0:
                dp[s] = min(dp[s], dp[s - weight] + value)

Items with a count limit (LC 2585): a question type with count copies offers choosing 1..count of them.
Only a prefix of each pile (LC 2218): taking x coins from a pile is worth its prefix sum, and x is the option.
Transform a number, then pick it (LC 4040, 4041): list the values a number can become and the steps each takes; those are its options.

Common Mistakes
#

Treating every coin problem as the same recurrence.
Using forward iteration for 0/1 items and accidentally reusing them.
Using backward iteration for unbounded counting and losing reuse.
Confusing dp[0] = 0 for min-count with dp[0] = 1 for counting.
Solving exact target only when the answer is closest half, as in partition problems.