LeetCode - Multiple Knapsack Problems

Medium

1155. Number of Dice Rolls With Target Sum

多重 / 分組背包基本概念

多重背包通常是：每種物品有使用次數限制
分組背包通常是：每一組裡只能選一個

1155 Number of Dice Rolls With Target Sum 比較接近分組背包：

• 有 n 顆骰子
• 每顆骰子都一定要選一個面
• 每顆骰子的可選值是 1 ~ k
• 問最後總和等於 target 的方法數

所以可以把每一顆骰子視為一組
每一組裡面有 k 種選擇

我的另一篇文章有解說各種背包問題的思路，底家 XD：

Algorithm - DP Knapsack

---

1155. Number of Dice Rolls With Target Sum

題目

You have n dice, and each die has k faces numbered from 1 to k.

Given three integers n, k, and target, return the number of possible ways out of the k^n total ways to roll the dice, so the sum of the face-up numbers equals target.

Since the answer may be too large, return it modulo .

Example 1

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces. There is only one way to get a sum of 3.

Example 2

Input: n = 2, k = 6, target = 7
Output: 6
Explanation: You throw two dice, each with 6 faces. There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3

Input: n = 30, k = 30, target = 500
Output: 222616187
Explanation: The answer must be returned modulo .

Constraints

• 1 <= n, k <= 30
• 1 <= target <= 1000

解題思路

這題可以視為分組背包
每一顆骰子是一組，每組都要選一個面

• DP 定義：

  • dp[i][now]：使用 i 顆骰子，湊出總和 now 的方法數

• 初始化：

  • dp[0][0] = 1
  • 代表使用 0 顆骰子湊出 0 有一種方法

• 狀態轉移：

  • 第 i 顆骰子可以擲出 1 ~ k
  • 假設這次擲出 j
  • 那麼前 i-1 顆骰子就需要湊出 now - j

• 因此：

  • dp[i][now] += dp[i-1][now-j]

• 因為是方法數問題

  • 每次更新都要取 modulo

• 最後答案為：
  dp[n][target]

Solution Code

Time Complexity
O(n × k × target)

Space Complexity
O(n × target)

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        vector<vector<long long int>> dp(n+1, vector<long long int>(target+1, 0)); // dp[n][k] 第一維是用了多少個少子，第二維是骰子面的值
        const int mod = 1e9 + 7;

        dp[0][0] = 1;

        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= k; ++j){
                for(int now = target; now >= j; --now){
                    dp[i][now] = (dp[i][now] + dp[i-1][now - j]) % mod;
                }
            }
        }

        return dp[n][target];
    }
};

---

Conclusion

這類題目和 0/1 背包、完全背包最大的差異在於「選擇限制」

• 0/1 背包：

  • 每個物品只能選一次

• 完全背包：

  • 每個物品可以選無限次

• 多重背包：

  • 每個物品可以選有限次

• 分組背包：

  • 每一組裡通常只能選一個

1155 Number of Dice Rolls With Target Sum 可以看成分組背包：
每顆骰子是一組，每一組都要從 1 ~ k 中選一個面，最後統計總和為 target 的方法數