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
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.
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.
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];
}
