获得分数的方法数

标签: 数组 动态规划

难度: Hard

考试中有 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

Submission

运行时间: 216 ms

内存: 18.6 MB

from typing import List

mod = 1e9 + 7

# dp[i][j] = dp[i - 1][j] + dp[i - 1][j - t] + ... + dp[i - 1][j - 2
# t] + dp[i - 1][j - 3
# t] + dp[i - 1][nt]
# dp[i][j - t] = dp[i - 1][j - t] + dp[i - 1][j - 2
# t] ...
# dp[i - 1][(n + 1)
# t]
# dp[i][j] = dp[i - 1][j] - dp[i - 1][(n + 1)t] + dp[i][j - t]


from typing import List

class Solution:
    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:
        n = len(types)
        types.insert(0, [0, 0])
        dp = [[0] * (target + 1) for _ in range(n + 1)]
        dp[0][0] = 1

        for i in range(1, n + 1):
            cnt = types[i][0]
            mark = types[i][1]

            for j in range(target + 1):
                dp[i][j] = dp[i - 1][j]

                if (cnt + 1) * mark <= j:
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - (cnt + 1) * mark] + mod) % mod

                if mark <= j:
                    dp[i][j] = (dp[i][j] + dp[i][j - mark]) % mod

        return int(dp[n][target])

Explain

本题解使用动态规划来解决这个问题。我们定义 dp[i][j] 为考虑到第 i 种类型的题目时，恰好得到 j 分的方法数。初始状态 dp[0][0] = 1，意味着不选择任何题目时，得分为 0 的方法有一种。对于每种类型的题目，我们更新 dp 数组，计算使用这种类型的题目可以获得的不同分数的方法数。对于每种类型的题目 types[i] = [counti, marksi]，我们需要处理可选数量和分值情况，利用前缀和思想优化计算过程，防止重复计算。最终，dp[n][target] 将给出恰好得到 target 分的方法数。

时间复杂度: O(n*target)

空间复杂度: O(n*target)

from typing import List

mod = 1e9 + 7

class Solution:
    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:
        n = len(types)
        types.insert(0, [0, 0])  # 插入一个哑节点方便处理边界问题
        dp = [[0] * (target + 1) for _ in range(n + 1)]
        dp[0][0] = 1  # 初始化基础情况

        for i in range(1, n + 1):
            cnt = types[i][0]
            mark = types[i][1]

            for j in range(target + 1):
                dp[i][j] = dp[i - 1][j]  # 不使用第 i 种类型的题目

                if (cnt + 1) * mark <= j:
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - (cnt + 1) * mark] + mod) % mod  # 减去多计算的部分

                if mark <= j:
                    dp[i][j] = (dp[i][j] + dp[i][j - mark]) % mod  # 添加使用一个第 i 种类型题目的情况

        return int(dp[n][target])  # 返回恰好得到 target 分的方法数

Explore

插入一个哑节点types[0] = [0, 0]主要是为了处理边界情况，使得数组的索引与题目类型对应起来，方便计算。哑节点的引入使得dp数组的初始化更加直观，dp[0][0] = 1表示在不选择任何题目的情况下，得分为0的方法恰好有一种。这样设置后，可以避免在循环中进行复杂的边界判断，简化代码逻辑。

dp数组的初始化中dp[0][0]设为1是因为在不选择任何题目的情况下，得分为0的方法只有一种，即什么都不做。而对于dp[0][j]（j>0），它们的初值都应该是0，因为在不使用任何题目的情况下，不可能获得大于0的分数，因此得分为j（j>0）的方法数应为0。

递推公式中的`dp[i][j] = (dp[i][j] - dp[i - 1][j - (cnt + 1) * mark] + mod) % mod`这一步用于确保不会重复计算超过允许数量的题目。这里，`dp[i - 1][j - (cnt + 1) * mark]`代表使用超过允许的题目数量来达到某个分数的方法数，通过从当前累计值中减去这部分，确保每种类型的题目最多只被使用其允许的次数。`mod`用于处理可能出现的负数，保证结果始终为非负。

在更新dp数组时使用模运算mod是为了防止计算结果溢出并保持结果在合理的范围内。由于方法数可能非常大，直接计算和存储这些值可能导致整数溢出，使用模运算可以保证每一步的结果都在0到mod-1之间，确保计算结果的稳定性和准确性。此外，这也是一种常见的技术，用于满足竞赛和实际应用中的需求，以防止在大数运算中的数值问题。