Hard

题目描述

有一场考试，包含 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 分，你可以选择以下七种方法之一：
- 解决第 0 种类型的 6 道题目：1 + 1 + 1 + 1 + 1 + 1 = 6
- 解决第 0 种类型的 4 道题目和第 1 种类型的 1 道题目：1 + 1 + 1 + 1 + 2 = 6
- 解决第 0 种类型的 2 道题目和第 1 种类型的 2 道题目：1 + 1 + 2 + 2 = 6
- 解决第 0 种类型的 3 道题目和第 2 种类型的 1 道题目：1 + 1 + 1 + 3 = 6
- 解决第 0 种类型的 1 道题目、第 1 种类型的 1 道题目和第 2 种类型的 1 道题目：1 + 2 + 3 = 6
- 解决第 1 种类型的 3 道题目：2 + 2 + 2 = 6
- 解决第 2 种类型的 2 道题目：3 + 3 = 6

示例 2：

输入：target = 5, types = [[50,1],[50,2],[50,5]]
输出：4

示例 3：

输入：target = 18, types = [[6,1],[3,2],[2,3]]
输出：1

约束条件：

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

解题思路

这是一个典型的分组背包问题。对于每种类型的题目，我们可以选择做0道到该类型最大数量的题目，每种选择对应不同的得分。

解题思路：

  1. 状态定义：使用动态规划，设 dp[i][j] 表示考虑前 i 种类型的题目，恰好得到 j 分的方法数。

  2. 状态转移：对于第 i 种类型的题目，我们可以选择做 k 道（其中 0 ≤ k ≤ types[i][0]）。如果做 k 道题目，得分为 k * types[i][1]。因此：

    dp[i][j] = sum(dp[i-1][j - k * marks]) for k in range(min(count, j // marks) + 1)

  3. 空间优化：由于每次状态转移只依赖于前一行，我们可以使用一维数组进行空间优化。为了避免重复计算，需要从大到小更新。

  4. 初始化：dp[0] = 1，表示得到0分有一种方法（不做任何题目）。

这种方法的时间复杂度相对较优，因为我们只需要遍历每种类型的题目一次，对于每种类型，再遍历所有可能的选择数量。

推荐解法：使用一维DP数组进行空间优化的分组背包解法。

代码实现

class Solution {
public:
    int waysToReachTarget(int target, vector<vector<int>>& types) {
        const int MOD = 1e9 + 7;
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        
        for (auto& type : types) {
            int count = type[0], marks = type[1];
            for (int j = target; j >= marks; j--) {
                for (int k = 1; k <= count && k * marks <= j; k++) {
                    dp[j] = (dp[j] + dp[j - k * marks]) % MOD;
                }
            }
        }
        
        return dp[target];
    }
};

class Solution:
    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:
        MOD = 10**9 + 7
        dp = [0] * (target + 1)
        dp[0] = 1
        
        for count, marks in types:
            for j in range(target, marks - 1, -1):
                for k in range(1, min(count, j // marks) + 1):
                    dp[j] = (dp[j] + dp[j - k * marks]) % MOD
        
        return dp[target]

public class Solution {
    public int WaysToReachTarget(int target, int[][] types) {
        const int MOD = 1000000007;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        
        foreach (var type in types) {
            int count = type[0], marks = type[1];
            for (int j = target; j >= marks; j--) {
                for (int k = 1; k <= count && k * marks <= j; k++) {
                    dp[j] = (dp[j] + dp[j - k * marks]) % MOD;
                }
            }
        }
        
        return dp[target];
    }
}

var waysToReachTarget = function(target, types) {
    const MOD = 1e9 + 7;
    const dp = new Array(target + 1).fill(0);
    dp[0] = 1;
    
    for (const [count, marks] of types) {
        for (let j = target; j >= marks; j--) {
            for (let k = 1; k <= count && k * marks <= j; k++) {
                dp[j] = (dp[j] + dp[j - k * marks]) % MOD;
            }
        }
    }
    
    return dp[target];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × target × max(count)) 其中 n 是题目类型数量
空间复杂度O(target) 使用一维DP数组

相关题目