获得分数的方法数

题目

2585. 获得分数的方法数

---

考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道，每道题目对应 marksi 分。

返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 10^9 +7 取余。

注意，同类型题目无法区分。

• 比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。

示例 1：

输入：target = 6, types = [[6,1],[3,2],[2,3]]
输出：7
解释：要获得 6 分，你可以选择以下七种方法之一：
- 解决 6 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 + 1 = 6
- 解决 4 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 1 + 2 = 6
- 解决 2 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 1 + 2 + 2 = 6
- 解决 3 道第 0 种类型的题目和 1 道第 2 种类型的题目：1 + 1 + 1 + 3 = 6
- 解决 1 道第 0 种类型的题目、1 道第 1 种类型的题目和 1 道第 2 种类型的题目：1 + 2 + 3 = 6
- 解决 3 道第 1 种类型的题目：2 + 2 + 2 = 6
- 解决 2 道第 2 种类型的题目：3 + 3 = 6

示例 2：

输入：target = 5, types = [[50,1],[50,2],[50,5]]
输出：4
解释：要获得 5 分，你可以选择以下四种方法之一：
- 解决 5 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 = 5
- 解决 3 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 2 = 5
- 解决 1 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 2 + 2 = 5
- 解决 1 道第 2 种类型的题目：5

示例 3：

输入：target = 18, types = [[6,1],[3,2],[2,3]]
输出：1
解释：只有回答所有题目才能获得 18 分。

提示：

• 1 <= target <= 1000
• n == types.length
• 1 <= n <= 50
• types[i].length == 2
• 1 <= counti, marksi <= 50

题解

方法一：

思路

分组背包，不同于01背包，01背包的物品只有选和不选两种，而分组背包的物品有一个选取的上限w，你可以选0次，1次，。。。，w次。
也可以认为01背包是分组背包的特殊情况，w取1。

现在n种题目可以认为就是物品种类。
每种题目的分值代表物品的价值。
每种题目的个数为背包物品选取的次数。

定义$f_{i,j}$为前i种物品选取后价值为j的选取种数。

$f_{0,0} = 1$

$f_{i,j} = \sum \limits_{k=0}^{count_{i}} f_{i-1, j-k*mark_i}$

代码

class Solution {
public:
    using ll = long long;
    const ll MOD = 1e9+7;
    int waysToReachTarget(int m, vector<vector<int>>& types) {
        int n = types.size();
        vector<vector<ll>> f(n+1,vector<ll>(m+1, 0));
        f[0][0] = 1;
        for (int i=1; i<=n; i++) {
            for (int k=0; k<=types[i-1][0]; k++) {
                for (int j=k*types[i-1][1]; j<=m; j++) {
                    f[i][j] += f[i-1][j-k*types[i-1][1]];
                    f[i][j] %= MOD;
                }
            }
        }
        return f[n][m];
    }
};