How do I approach the 'Number of Ways to Earn Points' problem?

This problem can be approached using dynamic programming, where you keep track of possible ways to achieve target points using the given question types.

What is the time complexity of solving the 'Number of Ways to Earn Points' problem?

The time complexity is O(n * target), where n is the number of question types and target is the required score.

How do I handle large numbers in this problem?

Since the result may be large, use modulo 10^9 + 7 during calculations to prevent overflow and ensure the solution fits within the problem constraints.

What should I consider when using dynamic programming for this problem?

Ensure you handle state transitions carefully for each question type and optimize space usage by keeping the dp array manageable.

What are the key challenges in this problem?

The main challenge is efficiently updating the dp array for multiple question types, ensuring correctness while dealing with large values.

#2585

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

获得分数的方法数

考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [count i , marks i ] 表示第 i 种类型的题目有 count i 道，每道题目对应 marks i 分。返回你在考试中恰好得到 target …

数组动态规划

题目描述

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

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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示前 $i$ 种类型的题目中，恰好得到 $j$ 分的方法数。初始时 $f[0][0] = 1$ ，其余 $f[i][j] = 0$ 。答案即为 $f[n][target]$ 。

我们可以枚举第 $i$ 种类型的题目，假设该类型题目的数量为 $count$ ，分数为 $marks$ ，那么我们可以得到如下状态转移方程：

f[i][j] = \sum_{k=0}^{count} f[i-1][j-k \times marks]

其中 $k$ 表示第 $i$ 种类型的题目的数量。

最终的答案即为 $f[n][target]$ 。注意答案可能很大，需要对 $10^9 + 7$ 取模。

时间复杂度 $O(n \times target \times count)$ ，空间复杂度 $O(n \times target)$ 。其中 $n$ 为题目类型的数量；而 $target$ 和 $count$ 分别为题目的目标分数和每种类型题目的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:
        n = len(types)
        mod = 10**9 + 7
        f = [[0] * (target + 1) for _ in range(n + 1)]
        f[0][0] = 1
        for i in range(1, n + 1):
            count, marks = types[i - 1]
            for j in range(target + 1):
                for k in range(count + 1):
                    if j >= k * marks:
                        f[i][j] = (f[i][j] + f[i - 1][j - k * marks]) % mod
        return f[n][target]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Strong candidates will recognize that this is a state transition dynamic programming problem.
question_mark
Candidates should efficiently handle large numbers and modulo operations.
question_mark
An ideal solution will be able to justify their approach and optimize space usage.

warning

常见陷阱

外企场景

error
Incorrect handling of the modulo operation, leading to overflow.
error
Failure to correctly iterate over all possible question combinations.
error
Not considering the constraints of the problem, such as the indistinguisability of questions of the same type.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Different limits for target and types array size.
arrow_right_alt
Variation in question types where mark values are significantly larger.
arrow_right_alt
Adding constraints on the count of questions for each type, such as having more than 50.

help

常见问题

外企场景

继续练习

#2581 统计可能的树根数目 #2573 找出对应 LCP 矩阵的字符串 #2597 美丽子集的数目