LC 518 & LC 377 (with template)

Solution to LeetCode 518 Coin Change II and LeetCode 377 Combination Sum IV.

LeetCode 518

Coin Change II (Medium) [link]

Define dp[j] as the number of combination with a sum of j. The recurrence relation is dp[j] += dp[j-coins[i]]. The base case dp[0]=1 meaning there is only one combination that can have a sum of 0.

The outer for loop is iterating the values of coins, and the inner for loop is iterating the capacities.

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount+1)
        dp[0] = 1
        for i in range(len(coins)):
            for j in range(coins[i], amount+1): # if the knapsack can take it
                dp[j] += dp[j-coins[i]]
        return dp[amount]

Note that if we want to count the number of combinations, the outer for loop should iterate through the items and inner for loop should iterate through the capacities. Otherwise, if we want to count the number of permutations, the outer for loop should iterate through the capacities and inner for loop should iterate through the items.

LeetCode 377

Combination Sum IV (Medium) [link]

Note that different sequences are counted as different permutations. So the outer loop should iterate through capacities and the inner loop should iterate through items.

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target+1)
        dp[0]=1
        for j in range(1, target+1):
            for i in range(len(nums)):
                if nums[i] <= j: # if the knapsack can take it
                    dp[j] += dp[j-nums[i]]
        return dp[target]

Template of 0-x Knapsack Problem

Brief summary of knapsack problems:

• 0-1 knapsack problem:

  • 2-d dp array:
    • Outer for loop is iterating items, inner for loop is iterating capacities of knapsack. They CAN switch the position.
  • 1-d dp array:
    • Outer for loop is iterating items, inner for loop is iterating capacities of knapsack. They CANNOT switch the position.

• 0-x knapsack problem:

  • 1-d dp array or 2-d dp array:

    Outer for loop is iterating items, inner for loop is iterating capacities of knapsack. They CAN switch the position.

  • Since we can have multiple copies of the same item, the inner for loop should NOT be in the reverse order any more.

O-x Knapsack code template

# loop items before iterating capacities
def test_complete_pack1():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bag_weight = 4

    dp = [0]*(bag_weight + 1)

    for i in range(len(weight)):
        for j in range(weight[i], bag_weight + 1):
              # recurrence relation
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    
    return dp[bag_weight]

# loop capacities before iterating items
def test_complete_pack2():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bag_weight = 4

    dp = [0]*(bag_weight + 1)

    for j in range(bag_weight + 1):
        for i in range(len(weight)):
            if j >= weight[i]: 
                  # recurrence relation
                  dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    
    return dp[bag_weight]