class Solution {
public:
int waysToReachTarget(int target, vector<vector<int>>& types) {
}
};
6310. 获得分数的方法数
考试中有 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 <= 1000n == types.length1 <= n <= 50types[i].length == 21 <= counti, marksi <= 50原站题解
golang 解法, 执行用时: 36 ms, 内存消耗: 2.6 MB, 提交时间: 2023-04-02 12:32:37
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]
}
cpp 解法, 执行用时: 72 ms, 内存消耗: 7.8 MB, 提交时间: 2023-04-02 12:32:26
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];
}
};
java 解法, 执行用时: 60 ms, 内存消耗: 39.6 MB, 提交时间: 2023-04-02 12:32:16
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];
}
}
python3 解法, 执行用时: 1240 ms, 内存消耗: 15 MB, 提交时间: 2023-04-02 12:32:05
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]