Welcome to Subscribe On Youtube
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.

class Solution { public int waysToReachTarget(int target, int[][] types) { int n = types.length; final int mod = (int) 1e9 + 7; int[][] f = new int[n + 1][target + 1]; f[0][0] = 1; for (int i = 1; i <= n; ++i) { int count = types[i  1][0], marks = types[i  1][1]; for (int j = 0; j <= target; ++j) { for (int k = 0; k <= count; ++k) { if (j >= k * marks) { f[i][j] = (f[i][j] + f[i  1][j  k * marks]) % mod; } } } } return f[n][target]; } }

class Solution { public: int waysToReachTarget(int target, vector<vector<int>>& types) { int n = types.size(); const int mod = 1e9 + 7; int f[n + 1][target + 1]; memset(f, 0, sizeof(f)); f[0][0] = 1; for (int i = 1; i <= n; ++i) { int count = types[i  1][0], marks = types[i  1][1]; for (int j = 0; j <= target; ++j) { for (int k = 0; k <= count; ++k) { if (j >= k * marks) { f[i][j] = (f[i][j] + f[i  1][j  k * marks]) % mod; } } } } return f[n][target]; } };

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]

func waysToReachTarget(target int, types [][]int) int { n := len(types) f := make([][]int, n+1) for i := range f { f[i] = make([]int, target+1) } f[0][0] = 1 const mod = 1e9 + 7 for i := 1; i <= n; i++ { count, marks := types[i1][0], types[i1][1] for j := 0; j <= target; j++ { for k := 0; k <= count; k++ { if j >= k*marks { f[i][j] = (f[i][j] + f[i1][jk*marks]) % mod } } } } return f[n][target] }

function waysToReachTarget(target: number, types: number[][]): number { const n = types.length; const mod = 10 ** 9 + 7; const f: number[][] = Array.from({ length: n + 1 }, () => Array(target + 1).fill(0)); f[0][0] = 1; for (let i = 1; i <= n; ++i) { const [count, marks] = types[i  1]; for (let j = 0; j <= target; ++j) { for (let k = 0; k <= count; ++k) { if (j >= k * marks) { f[i][j] = (f[i][j] + f[i  1][j  k * marks]) % mod; } } } } return f[n][target]; }