2585-获得分数的方法数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

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

返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 109 +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

分组背包模板题。

定义 f[i][j] 表示用前 i 种题目恰好组成 j 分的方案数。

对于第 i 种题目，枚举做 k 道题目，则子问题为「前 i-1 种题目恰好组成 j-k\cdot \textit{marks}_i 分的方案数」，因此有

f[i][j] = \sum\limits_{k=0} f[i-1][j-k\cdot \textit{marks}_i]

注意 k 不能超过 count}_i，且 j-k\cdot \textit{marks}_i\ge 0。

代码实现时可以像 0-1 背包那样，压缩成一维，具体可以看【基础算法精讲 18】 。

注：滚动优化后，k=0 就是 f[j]，无需计算。

附：本题视频讲解

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        f = [1] + [0] * target
        for count, marks in types:
            for j in range(target, 0, -1):
                for k in range(1, min(count, j // marks) + 1):
                    f[j] += f[j - k * marks]
                f[j] %= MOD
        return f[-1]
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int waysToReachTarget(int target, int[][] types) {
        var f = new int[target + 1];
        f[0] = 1;
        for (var p : types) {
            int count = p[0], marks = p[1];
            for (int j = target; j > 0; --j)
                for (int k = 1; k <= count && k <= j / marks; ++k)
                    f[j] = (f[j] + f[j - k * marks]) % MOD;
        }
        return f[target];
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    const int MOD = 1e9 + 7;
public:
    int waysToReachTarget(int target, vector<vector<int>> &types) {
        int f[target + 1];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (auto &p : types) {
            int count = p[0], marks = p[1];
            for (int j = target; j > 0; --j)
                for (int k = 1; k <= min(count, j / marks); ++k)
                    f[j] = (f[j] + f[j - k * marks]) % MOD;
        }
        return f[target];
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func waysToReachTarget(target int, types [][]int) int {
	const mod int = 1e9 + 7
	f := make([]int, target+1)
	f[0] = 1
	for _, p := range types {
		count, marks := p[0], p[1]
		for j := target; j > 0; j-- {
			for k := 1; k <= count && k <= j/marks; k++ {
				f[j] += f[j-k*marks]
			}
			f[j] %= mod
		}
	}
	return f[target]
}

复杂度分析

  • 时间复杂度：O(TS)，其中 T 为 target，S 为所有 count}_i 之和。
  • 空间复杂度：O(T)。

相似题目

思考题

如果同类型题目需要区分，要怎么做呢？

 Comments
On this page
2585-获得分数的方法数
  1. 复杂度分析
  2. 相似题目
  3. 思考题