背包 DP（0/1、完全背包、Coin Change）

# python
# LC 416 - Partition Equal Subset Sum
# IDEA: 0/1 knapsack on sums -- can a subset reach total / 2? inner loop backward = each num once
# time = O(n * target), space = O(target)
def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:                    # an odd total cannot split into two equal halves
        return False
    target = total // 2
    dp = [False] * (target + 1)           # dp[s] = some subset of the nums so far sums to s
    dp[0] = True                          # the empty subset
    for num in nums:
        for s in range(target, num - 1, -1):   # BACKWARD: dp[s - num] is still the old row
            if dp[s - num]:
                dp[s] = True
    return dp[target]

// java
// LC 416 - Partition Equal Subset Sum
// IDEA: 0/1 knapsack on sums -- can a subset reach total / 2? inner loop backward = each num once
// time = O(n * target), space = O(target)
public boolean canPartition(int[] nums) {
    int total = 0;
    for (int num : nums) {
        total += num;
    }
    if (total % 2 == 1) {                  // an odd total cannot split into two equal halves
        return false;
    }
    int target = total / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;                          // the empty subset
    for (int num : nums) {
        for (int s = target; s >= num; s--) {   // BACKWARD: dp[s - num] is still the old row
            if (dp[s - num]) {
                dp[s] = true;
            }
        }
    }
    return dp[target];
}

can we reach s?        dp[s] = dp[s] or dp[s - w]           base dp[0] = True
how many subsets?      dp[s] += dp[s - w]                   base dp[0] = 1     (LC 494)
best value within s?   dp[s] = max(dp[s], dp[s - w] + v)    base dp[*] = 0     (classic knapsack)

forward  s=3: dp[3] = dp[0] = T
         s=6: dp[6] = dp[3] = T    <- dp[3] was set by THIS item a moment ago: 3 used twice
         s=9: dp[9] = dp[6] = T    <- and three times
backward s=9: dp[9] = dp[6] (old, F)
         s=6: dp[6] = dp[3] (old, F)
         s=3: dp[3] = dp[0] = T    <- the only sum one 3 can make

# python
# LC 416 - Partition Equal Subset Sum (top-down)
# IDEA: can(i, r) = can some subset of nums[i:] sum to r? take nums[i] or skip it; memoise on (i, r)
# time = O(n * target), space = O(n * target)
def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2
    memo = {}

    def can(i, remaining):
        if remaining == 0:
            return True
        if i == len(nums) or remaining < 0:
            return False
        key = (i, remaining)
        if key in memo:
            return memo[key]
        result = can(i + 1, remaining - nums[i]) or can(i + 1, remaining)   # take, or skip
        memo[key] = result
        return result

    return can(0, target)

# python
# IDEA: dp[i][w] = best value using the first i items within capacity w
# time = O(n * W), space = O(n * W)
def knapsack_01_2d(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight, value = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]                               # skip item i
            if weight <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value)   # take item i
    return dp[n][capacity]

# python
# LC 518 - Coin Change II
# IDEA: coins OUTER (each multiset built in one canonical order), amount inner FORWARD (reuse)
# time = O(n * amount), space = O(amount)
def change(amount, coins):
    dp = [0] * (amount + 1)        # dp[a] = combinations of the coins so far that sum to a
    dp[0] = 1                      # one way to make 0: take nothing
    for coin in coins:
        for a in range(coin, amount + 1):   # forward: dp[a - coin] may already use this coin
            dp[a] += dp[a - coin]
    return dp[amount]

// java
// LC 518 - Coin Change II
// IDEA: coins OUTER (each multiset built in one canonical order), amount inner FORWARD (reuse)
// time = O(n * amount), space = O(amount)
public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;                                  // one way to make 0: take nothing
    for (int coin : coins) {
        for (int a = coin; a <= amount; a++) {  // forward: dp[a - coin] may already use this coin
            dp[a] += dp[a - coin];
        }
    }
    return dp[amount];
}

start          dp = [1, 0, 0, 0]
coin 1  a=1..3 dp = [1, 1, 1, 1]     {1} {1,1} {1,1,1}
coin 2  a=2    dp[2] += dp[0] -> 2   {1,1} {2}
        a=3    dp[3] += dp[1] -> 2   {1,1,1} {1,2}   -- no {2,1}: coin 1 is finished
answer  dp[3] = 2

# python
# LC 377 - Combination Sum IV
# IDEA: amount OUTER, numbers inner -- dp[t] sums over the number placed LAST, so orders differ
# time = O(n * target), space = O(target)
def combinationSum4(nums, target):
    dp = [0] * (target + 1)        # dp[t] = ordered sequences summing to t
    dp[0] = 1                      # the empty sequence
    for t in range(1, target + 1):
        for num in nums:           # try every number as the last one
            if t - num >= 0:
                dp[t] += dp[t - num]
    return dp[target]

// java
// LC 377 - Combination Sum IV
// IDEA: amount OUTER, numbers inner -- dp[t] sums over the number placed LAST, so orders differ
// time = O(n * target), space = O(target)
public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;                                  // the empty sequence
    for (int t = 1; t <= target; t++) {
        for (int num : nums) {                  // try every number as the last one
            if (t - num >= 0) {
                dp[t] += dp[t - num];
            }
        }
    }
    return dp[target];
}

t=1  last 1: dp[0]=1                    dp[1] = 1   {1}
t=2  last 1: dp[1]=1, last 2: dp[0]=1   dp[2] = 2   {1,1} {2}
t=3  last 1: dp[2]=2, last 2: dp[1]=1   dp[3] = 3   {1,1,1} {2,1} {1,2}

# python
# LC 322 - Coin Change
# IDEA: dp[a] = min over the last coin of dp[a - coin] + 1; INF = amount + 1 marks "unreachable"
# time = O(amount * n), space = O(amount)
def coinChange(coins, amount):
    INF = amount + 1                  # more coins than any real answer can use
    dp = [INF] * (amount + 1)         # dp[a] = fewest coins summing to exactly a
    dp[0] = 0                         # zero coins make 0
    for a in range(1, amount + 1):
        for coin in coins:
            if a - coin >= 0:         # the coin fits; dp[a - coin] is already final
                dp[a] = min(dp[a], dp[a - coin] + 1)
    return -1 if dp[amount] == INF else dp[amount]

// java
// LC 322 - Coin Change
// IDEA: dp[a] = min over the last coin of dp[a - coin] + 1; INF = amount + 1 marks "unreachable"
// time = O(amount * n), space = O(amount)
public int coinChange(int[] coins, int amount) {
    int INF = amount + 1;                       // more coins than any real answer can use
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;                                  // zero coins make 0
    for (int a = 1; a <= amount; a++) {
        for (int coin : coins) {
            if (a - coin >= 0) {                // the coin fits; dp[a - coin] is already final
                dp[a] = Math.min(dp[a], dp[a - coin] + 1);
            }
        }
    }
    return dp[amount] == INF ? -1 : dp[amount];
}

dp[capacity] = best value     ->   "how much have I packed?"     (Templates 1-4)
dp[difference] = best height  ->   "how unbalanced are the two piles?"

skip it            ->  (d,        taller)                 unchanged
put on TALLER      ->  (d + x,    taller + x)             the gap widens
put on SHORTER     ->  (|d - x|,  max(taller, shorter+x)) the gap closes, and may flip sides
                       where shorter = taller - d

# python
# LC 956 - Tallest Billboard
# IDEA: dict from difference -> tallest "taller side"; only reachable differences are stored
# time = O(n * sum), space = O(sum)
def tallestBillboard(rods):
    dp = {0: 0}                        # difference -> height of the taller support
    for x in rods:
        prev = dict(dp)                # snapshot: each rod is placed at most once
        for d, taller in prev.items():
            shorter = taller - d
            dp[d + x] = max(dp.get(d + x, 0), taller + x)       # x on the taller side
            nd = abs(d - x)                                    # x on the shorter side
            dp[nd] = max(dp.get(nd, 0), max(taller, shorter + x))
    return dp[0]                       # difference 0 = equal supports

// java
// LC 956 - Tallest Billboard
// IDEA: key the table by the DIFFERENCE between the two supports, store the taller
//       support's height. Answer = dp[0], the best height at difference zero.
// time = O(n * sum), space = O(sum)
public int tallestBillboard(int[] rods) {
    int sum = 0;
    for (int r : rods) {
        sum += r;
    }
    int[] dp = new int[sum + 1];
    Arrays.fill(dp, -1);          // -1 = unreachable; 0 is a real, reachable height
    dp[0] = 0;
    for (int x : rods) {
        int[] prev = dp.clone();  // "skip x" is prev carried forward, already in dp
        for (int d = 0; d <= sum; d++) {
            if (prev[d] < 0) {
                continue;
            }
            int taller = prev[d];
            int shorter = taller - d;
            if (d + x <= sum) {                       // x joins the taller pile
                dp[d + x] = Math.max(dp[d + x], taller + x);
            }
            int nd = Math.abs(d - x);                 // x joins the shorter pile
            dp[nd] = Math.max(dp[nd], Math.max(taller, shorter + x));
        }
    }
    return dp[0];
}

start        {0: 0}
after 1      {0: 0, 1: 1}
after 2      {0: 0, 1: 2, 2: 2, 3: 3}
after 3      {0: 3, 1: 3, 2: 4, 3: 3, 4: 5, 5: 5, 6: 6}
after 6      {0: 6, 1: 6, 2: 7, 3: 6, ...}   -> dp[0] = 6, supports {6} and {1,2,3}

✅ snapshot         read prev, write into a copy   every option competes against the state BEFORE the item
✅ capacity OUTER   for s in W..0:                  dp[s-w] is a smaller index, not yet touched by this item
                        for (w, c) in group:
❌ options OUTER    for (w, c) in group:            option B reads a dp[] that option A has already updated
                        for s in W..w:

x, 2x, 4x, ...        k doublings, cost k   (stop past sum: it only grows)
x, x//2, x//4, ...    k halvings,  cost k   (stop at 0: it never helps a positive sum)

x = 10, sum = 13  ->  (10, 0), (5, 1), (2, 2), (1, 3)      20 is already over sum
x =  2, sum = 13  ->  (2, 0), (4, 1), (8, 2), (1, 1)

# python
# LC 4040 - Minimum Operations to Form Subset Sum I
# IDEA: group knapsack -- each x is a menu of (value, ops); a snapshot of dp lets at most one
#       entry per x be taken
# time = O(n * sum * log(max(x, sum))), space = O(sum)
def minOperations(nums, sum):
    INF = float('inf')
    dp = [INF] * (sum + 1)                 # dp[s] = min ops for a subset summing to s
    dp[0] = 0
    for x in nums:
        options = []                       # the menu for x: (value, ops)
        value, op = x, 0
        while value <= sum:                # x itself (0 ops), 2x, 4x, ...
            options.append((value, op))
            value *= 2
            op += 1
        value, op = x, 0
        while value > 0:                   # x//2, x//4, ...
            value //= 2
            op += 1
            if 0 < value <= sum:
                options.append((value, op))
        new_dp = dp[:]                     # snapshot: every option reads the pre-x state
        for value, cost in options:
            for s in range(value, sum + 1):
                if dp[s - value] != INF:
                    new_dp[s] = min(new_dp[s], dp[s - value] + cost)
        dp = new_dp
    return -1 if dp[sum] == INF else dp[sum]

// java
// LC 4040 - Minimum Operations to Form Subset Sum I
// IDEA: same group knapsack, written in place with the capacity loop OUTER and backward
// time = O(n * sum * log(max(x, sum))), space = O(sum)
public int minOperations(int[] nums, int sum) {
    final int INF = Integer.MAX_VALUE / 2;     // + cost cannot overflow
    int[] dp = new int[sum + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;
    for (int x : nums) {
        List<int[]> options = new ArrayList<>();
        long value = x;
        int op = 0;
        while (value <= sum) {                 // x itself (0 ops), 2x, 4x, ...
            options.add(new int[]{(int) value, op});
            value *= 2;
            op++;
        }
        value = x;
        op = 0;
        while (value > 0) {                    // x/2, x/4, ...
            value /= 2;
            op++;
            if (value > 0 && value <= sum) {
                options.add(new int[]{(int) value, op});
            }
        }
        for (int s = sum; s >= 0; s--) {       // capacity OUTER, backward
            for (int[] option : options) {     // options INNER: one form per x
                int v = option[0];
                int cost = option[1];
                if (s >= v && dp[s - v] != INF) {
                    dp[s] = Math.min(dp[s], dp[s - v] + cost);
                }
            }
        }
    }
    return dp[sum] >= INF ? -1 : dp[sum];
}

start        {0:0}
after 10     {0:0, 1:3, 2:2, 5:1, 10:0}
after 2      {0:0, 1:1, 2:0, 3:3, 4:1, 5:1, 6:2, 7:1, 8:2, 9:2, 10:0, 11:1, 12:0, 13:3}
                                              dp[13] = dp[5] + 2 = 1 + 2 -> 10->5 and 2->4->8

# python
# LC 1049 - Last Stone Weight II
# IDEA: 0/1 subset sum up to total // 2; the answer is total - 2 * (largest reachable sum)
# time = O(n * total), space = O(total)
def lastStoneWeightII(stones):
    total = sum(stones)
    half = total // 2
    dp = [False] * (half + 1)             # dp[s] = some subset of the stones sums to s
    dp[0] = True
    for stone in stones:
        for s in range(half, stone - 1, -1):   # backward: each stone once
            if dp[s - stone]:
                dp[s] = True
    for s in range(half, -1, -1):         # the most balanced split
        if dp[s]:
            return total - 2 * s

// java
// LC 1049 - Last Stone Weight II
// IDEA: 0/1 subset sum up to total / 2; the answer is total - 2 * (largest reachable sum)
// time = O(n * total), space = O(total)
public int lastStoneWeightII(int[] stones) {
    int total = 0;
    for (int stone : stones) {
        total += stone;
    }
    int half = total / 2;
    boolean[] dp = new boolean[half + 1];
    dp[0] = true;
    for (int stone : stones) {
        for (int s = half; s >= stone; s--) {   // backward: each stone once
            if (dp[s - stone]) {
                dp[s] = true;
            }
        }
    }
    for (int s = half; s >= 0; s--) {           // the most balanced split
        if (dp[s]) {
            return total - 2 * s;
        }
    }
    return total;                               // unreachable: dp[0] is always true
}

stones = [2, 7, 4, 1, 8, 1], total = 23, half = 11

after 2      reachable {0, 2}
after 7      reachable {0, 2, 7, 9}
after 4      reachable {0, 2, 4, 6, 7, 9, 11}
...          11 stays reachable  ->  answer = 23 - 2 * 11 = 1

# python
# LC 494 - Target Sum
# IDEA: reduce "assign +/-" to "count subsets summing to (total + T) / 2", then 0/1 knapsack
# time = O(n * P), space = O(P)
def findTargetSumWays(nums, target):
    total = sum(nums)
    if abs(target) > total or (total + target) % 2 == 1:   # P negative or not an integer
        return 0
    plus = (total + target) // 2
    dp = [0] * (plus + 1)                 # dp[s] = subsets of the nums so far summing to s
    dp[0] = 1                             # the empty subset
    for num in nums:
        for s in range(plus, num - 1, -1):    # backward: each num once
            dp[s] += dp[s - num]
    return dp[plus]

// java
// LC 494 - Target Sum
// IDEA: reduce "assign +/-" to "count subsets summing to (total + T) / 2", then 0/1 knapsack
// time = O(n * P), space = O(P)
public int findTargetSumWays(int[] nums, int target) {
    int total = 0;
    for (int num : nums) {
        total += num;
    }
    if (Math.abs(target) > total || (total + target) % 2 != 0) {   // P negative or not an integer
        return 0;
    }
    int plus = (total + target) / 2;
    int[] dp = new int[plus + 1];
    dp[0] = 1;                                  // the empty subset
    for (int num : nums) {
        for (int s = plus; s >= num; s--) {     // backward: each num once
            dp[s] += dp[s - num];
        }
    }
    return dp[plus];
}

Does one item offer SEVERAL mutually exclusive options?
│
├─ YES ──► Group Knapsack  [4040, 1155, 2218, 2585]
│          for group in groups:
│              for w in range(W, -1, -1):             # CAPACITY outer, backward
│                  for (weight, cost) in group:       # options inner
│          └─ or snapshot dp and let every option read the pre-group state
│          └─ options-outer + in-place dp is the classic bug: two forms of one item
│
└─ NO  ──► Is each item reusable?
    │
    ├─ NO  ──► 0/1 Knapsack
    │          for item in items:
    │              for w in range(W, weight-1, -1):     # BACKWARD
    │          └─ asks "can we hit the sum?"  -> boolean dp
    │          └─ asks "how many ways?"       -> dp[j] += dp[j-w]
    │          └─ asks "best value?"          -> dp[j] = max(dp[j], dp[j-w]+v)
    │
    └─ YES ──► Does order matter?
               │
               ├─ NO  (combinations, {1,2} == {2,1})  ──► items outer, amount inner  [518]
               ├─ YES (permutations, {1,2} != {2,1})  ──► amount outer, items inner  [377]
               └─ Min/max only (order irrelevant)     ──► either nesting             [322, 279]