DP Knapsack / Subset Pattern¶

# 2D version
dp = [[0] * (target + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for c in range(target + 1):
        dp[i][c] = dp[i-1][c]  # skip
        if c >= nums[i-1]:
            dp[i][c] = max(dp[i][c], dp[i-1][c - nums[i-1]] + nums[i-1])  # take

# 1D version (iterate capacity backwards for 0/1 knapsack)
dp = [0] * (target + 1)
for num in nums:
    for c in range(target, num - 1, -1):  # backwards!
        dp[c] = max(dp[c], dp[c - num] + num)

class Solution:
    """
    0/1 Knapsack: Can we select items to reach target sum?

    Key Insight: If total sum is S, we need to find a subset summing to S/2.
    If such a subset exists, the remaining elements also sum to S/2.

    State: dp[s] = True if sum s is achievable using some subset
    Transition: dp[s] = dp[s] or dp[s - num] (take or skip)
    Base: dp[0] = True (empty subset has sum 0)

    Why iterate backwards? Each number can only be used once.
    Forward iteration would use the same number multiple times.

    Time: O(n * sum) | Space: O(sum)
    """
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)

        # Odd sum can't be split evenly
        if total % 2 != 0:
            return False

        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True  # Empty subset

        for num in nums:
            # Iterate backwards to ensure each num used at most once
            for s in range(target, num - 1, -1):
                dp[s] = dp[s] or dp[s - num]

        return dp[target]

class Solution:
    """
    0/1 Knapsack: Count ways to reach target.

    Key Insight: Transform +/- assignment to subset selection.
    - Let P = sum of numbers with + sign
    - Let N = sum of numbers with - sign
    - P - N = target, P + N = total
    - Therefore: P = (target + total) / 2

    We need to count subsets summing to P (positive group).

    State: dp[s] = number of ways to form sum s
    Transition: dp[s] += dp[s - num]
    Base: dp[0] = 1 (one way: empty subset)

    Time: O(n * sum) | Space: O(sum)
    """
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)

        # Check feasibility
        if (total + target) % 2 != 0 or total + target < 0:
            return 0

        subset_sum = (total + target) // 2
        dp = [0] * (subset_sum + 1)
        dp[0] = 1  # One way to form sum 0

        for num in nums:
            # Backwards for 0/1 (each number used once)
            for s in range(subset_sum, num - 1, -1):
                dp[s] += dp[s - num]

        return dp[subset_sum]

class Solution:
    """
    Unbounded Knapsack: Minimum items to reach target.

    Key Differences from 0/1:
    - Coins can be reused → iterate forwards
    - Goal is minimize → use min() instead of sum/or
    - Initialize with infinity (impossible until proven otherwise)

    State: dp[a] = minimum coins to make amount a
    Transition: dp[a] = min(dp[a], dp[a - coin] + 1)
    Base: dp[0] = 0 (zero coins for amount 0)

    Why iterate forwards? To allow reusing coins.
    dp[a - coin] might already include the current coin.

    Time: O(n * amount) | Space: O(amount)
    """
    def coinChange(self, coins: List[int], amount: int) -> int:
        # Initialize with "impossible" value
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0  # Zero coins for amount 0

        for coin in coins:
            # Forward iteration: coins can be reused
            for a in range(coin, amount + 1):
                dp[a] = min(dp[a], dp[a - coin] + 1)

        return dp[amount] if dp[amount] != float('inf') else -1

class Solution:
    """
    Unbounded Knapsack: Count ways to reach target.

    Key Insight: Same as Coin Change but counting instead of minimizing.
    - Coins can be reused → forward iteration
    - Count ways → use += instead of min()
    - Combinations (not permutations) → coins outer, amount inner

    State: dp[a] = number of ways to make amount a
    Transition: dp[a] += dp[a - coin]
    Base: dp[0] = 1 (one way to make amount 0: use no coins)

    Why coins outer loop? To count combinations, not permutations.
    Amount outer would count [1,2] and [2,1] as different.

    Time: O(n * amount) | Space: O(amount)
    """
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1  # One way to make amount 0

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

        return dp[amount]

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

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

def can_partition(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):  # Backwards!
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

def count_subsets(nums: List[int], target: int) -> int:
    dp = [0] * (target + 1)
    dp[0] = 1

    for num in nums:
        for s in range(target, num - 1, -1):  # Backwards!
            dp[s] += dp[s - num]

    return dp[target]

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

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

    return dp[amount] if dp[amount] != float('inf') else -1

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

    for coin in coins:  # Coins outer for combinations
        for a in range(coin, amount + 1):  # Forwards!
            dp[a] += dp[a - coin]

    return dp[amount]

def target_sum_ways(nums: List[int], target: int) -> int:
    total = sum(nums)

    # Transform: P - N = target, P + N = total → P = (target + total) / 2
    if (total + target) % 2 != 0 or total + target < 0:
        return 0

    subset_target = (total + target) // 2
    return count_subsets(nums, subset_target)  # Use 0/1 count template

def knapsack_2d(items: List[Tuple[int, int]], capacity: int) -> int:
    """
    items: list of (weight, value)
    Returns: maximum value achievable within capacity
    """
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i-1][c]  # Skip item
            if c >= weight:
                dp[i][c] = max(dp[i][c], dp[i-1][c - weight] + value)  # Take item

    return dp[n][capacity]