2585. Number of Ways to Earn Points
Description
There is a test that has n
types of questions. You are given an integer target
and a 0indexed 2D integer array types
where types[i] = [count_{i}, marks_{i}]
indicates that there are count_{i}
questions of the i^{th}
type, and each one of them is worth marks_{i}
points.
Return the number of ways you can earn exactly target
points in the exam. Since the answer may be too large, return it modulo 10^{9} + 7
.
Note that questions of the same type are indistinguishable.
 For example, if there are
3
questions of the same type, then solving the1^{st}
and2^{nd}
questions is the same as solving the1^{st}
and3^{rd}
questions, or the2^{nd}
and3^{rd}
questions.
Example 1:
Input: target = 6, types = [[6,1],[3,2],[2,3]] Output: 7 Explanation: You can earn 6 points in one of the seven ways:  Solve 6 questions of the 0^{th} type: 1 + 1 + 1 + 1 + 1 + 1 = 6  Solve 4 questions of the 0^{th} type and 1 question of the 1^{st} type: 1 + 1 + 1 + 1 + 2 = 6  Solve 2 questions of the 0^{th} type and 2 questions of the 1^{st} type: 1 + 1 + 2 + 2 = 6  Solve 3 questions of the 0^{th} type and 1 question of the 2^{nd} type: 1 + 1 + 1 + 3 = 6  Solve 1 question of the 0^{th} type, 1 question of the 1^{st} type and 1 question of the 2^{nd} type: 1 + 2 + 3 = 6  Solve 3 questions of the 1^{st} type: 2 + 2 + 2 = 6  Solve 2 questions of the 2^{nd} type: 3 + 3 = 6
Example 2:
Input: target = 5, types = [[50,1],[50,2],[50,5]] Output: 4 Explanation: You can earn 5 points in one of the four ways:  Solve 5 questions of the 0^{th} type: 1 + 1 + 1 + 1 + 1 = 5  Solve 3 questions of the 0^{th} type and 1 question of the 1^{st} type: 1 + 1 + 1 + 2 = 5  Solve 1 questions of the 0^{th} type and 2 questions of the 1^{st} type: 1 + 2 + 2 = 5  Solve 1 question of the 2^{nd} type: 5
Example 3:
Input: target = 18, types = [[6,1],[3,2],[2,3]] Output: 1 Explanation: You can only earn 18 points by answering all questions.
Constraints:
1 <= target <= 1000
n == types.length
1 <= n <= 50
types[i].length == 2
1 <= count_{i}, marks_{i} <= 50
Solutions
Solution 1: Dynamic Programming
We define $f[i][j]$ to represent the number of methods to get $j$ points exactly from the first $i$ types of questions. Initially, $f[0][0] = 1$, and the rest $f[i][j] = 0$. The answer is $f[n][target]$.
We can enumerate the $i$th type of questions, suppose the number of questions of this type is $count$, and the score is $marks$. Then we can get the following state transition equation:
$$ f[i][j] = \sum_{k=0}^{count} f[i1][jk \times marks] $$
where $k$ represents the number of questions of the $i$th type.
The final answer is $f[n][target]$. Note that the answer may be very large and needs to be modulo $10^9 + 7$.
The time complexity is $O(n \times target \times count)$ and the space complexity is $O(n \times target)$. $n$ is the number of types of questions, and $target$ and $count$ are the target score and the number of questions of each type, respectively.









