Backpack

92t Backpack

Given an array representing item size [2, 3, 5, 7], the backpack size is 11. Return the max size we can fill in the given backpack.

• Use the package size as an array

• 1st loop the size array, second loop the volume from tail

• State: dp[i][j]代表前i個item在j size下可以裝下的最大數字

public int backPack(int m, int[] A) {
    int n = A.length;
    int[][] dp = new int[n+1][m+1];

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            dp[i][j] = dp[i-1][j];
            // 當背包空間足夠時
            if(j >= A[i-1]){
                                               // 找上一層原本的而不是更新過的
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j-A[i-1]] + A[i-1]);
            }
        }
    }
    return dp[n][m];
}

• Rolling array updates from tail

public int backPack(int m, int[] A) {
    int len = A.length;
    int[] dp = new int[m+1];

    for(int i=0; i<len; i++){
        for(int j=m; j>=0; j--){
            if(j >= A[i]){
                dp[j] = Math.max(dp[j], dp[j-A[i]] + A[i]);
            }
        }
    }
    return dp[m];
}

322 Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1

• $F(i)$ is computed as $min_{j=0 \ldots n-1}{F(i -c_j)} + 1$

• dp[ ] initiate all max int

• Coin 可以重複使用，outer loop coin 1~amount, inner loop 幣值

• See example

def coinChange(self, coins: List[int], amount: int) -> int:
    dp = [float('inf')] * (amount+1)
    dp[0] = 0
    
    for coin in coins:
        for j in range(coin, amount+1):
            dp[j] = min(dp[j], dp[j-coin]+1)
            
    return dp[amount] if dp[amount] != float('inf') else -1

# 如果要記錄coin 組成
def coinChange(self, coins: List[int], amount: int) -> int:
    dp = [(float('inf'), [])] * (amount+1)
    dp[0] = (0, [0] * len(coins)) # (# of coins, coin list)
    
    for i, coin in enumerate(coins):
        for j in range(coin, amount+1):
            if dp[j][0] > dp[j-coin][0] + 1:
              dp[j] = (dp[j-coin][0]+1, dp[j-coin][1].copy())
              dp[j][1][i] += 1
                
    return dp[amount][1] if dp[amount] != float('inf') else []

518 Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount

• Statment: dp[i][j]指前i種貨幣可以組成amount j 的方式個數

• Func: dp[i][j] = dp[i-1][j] + dp[i][j-coin[i]] if j>=coin[i]

• Init: dp[i][0] = 1

• Ans dp[m+1][n+1]

def change(self, amount: int, coins: List[int]) -> int:
    dp = [0] * (amount+1)
    dp[0] = 1
    
    for coin in coins:
        # 忽略 coin > j 的部分
        for j in range(coin, amount+1):
            dp[j] += dp[j-coin]
                
    return dp[amount]

1155. Number of Dice Rolls With Target Sum

You have d dice, and each die has f faces numbered 1, 2, ..., f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

Input: d = 2, f = 6, target = 7
Output: 6
Explanation: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Top-down DP

dp[i][j] = 在 i 個dice情況下達成 j 的combination

Runtime: O(d * f * target). Memory: O(d * target) for the memorization.

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/discuss/355894/Python-DP-with-memoization-explained

def numRollsToTarget(self, d: int, f: int, target: int) -> int:
    memo = {}
    def dp(d, target):
        if target < 0: return 0
        if d == 0:
            return 1 if target == 0 else 0
        if (d, target) in memo:
            return memo[(d, target)]
        to_return = 0
        for k in range(1, f+1):
            to_return += dp(d-1, target-k)
        memo[(d, target)] = to_return
        return to_return
    return dp(d, target) % (10**9 + 7)

Bottom-Up DP

Similar to coin change, dp[i][j]為在提供 i number 的情況下可以得到 j 的combination, 注意 dp2[i][j] 受限於dp1[i-1][j] + dp1[i-1][j-1], 並且執行了 d 個 dice 次數

Runtime: O(d *f * target).

Memory: O(target) as we only store counts for the last dice.

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/discuss/355940/C%2B%2B-Coin-Change-2

int numRollsToTarget(int d, int f, int target) {
  vector<int> dp(target + 1);
  dp[0] = 1;
  for (int i = 1; i <= d; ++i) {
    vector<int> dp1(target + 1);
    for (int j = 1; j <= f; ++j)
      for (auto k = j; k <= target; ++k)
        dp1[k] = (dp1[k] + dp[k - j]) % 1000000007;
    swap(dp, dp1);
  }
  return dp[target];
}