2585. Number of Ways to Earn Points Hard

1/**
2 * [2585] Number of Ways to Earn Points
3 *
4 * There is a test that has n types of questions. You are given an integer target and a 0-indexed 2D integer array types where types[i] = [counti, marksi] indicates that there are counti questions of the i^th type, and each one of them is worth marksi points.
5 * 
6 * 
7 * 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.
8 * Note that questions of the same type are indistinguishable.
9 * 
10 * 	For example, if there are 3 questions of the same type, then solving the 1^st and 2^nd questions is the same as solving the 1^st and 3^rd questions, or the 2^nd and 3^rd questions.
11 * 
12 *  
13 * <strong class="example">Example 1:
14 * 
15 * Input: target = 6, types = [[6,1],[3,2],[2,3]]
16 * Output: 7
17 * Explanation: You can earn 6 points in one of the seven ways:
18 * - Solve 6 questions of the 0^th type: 1 + 1 + 1 + 1 + 1 + 1 = 6
19 * - Solve 4 questions of the 0^th type and 1 question of the 1^st type: 1 + 1 + 1 + 1 + 2 = 6
20 * - Solve 2 questions of the 0^th type and 2 questions of the 1^st type: 1 + 1 + 2 + 2 = 6
21 * - Solve 3 questions of the 0^th type and 1 question of the 2^nd type: 1 + 1 + 1 + 3 = 6
22 * - 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
23 * - Solve 3 questions of the 1^st type: 2 + 2 + 2 = 6
24 * - Solve 2 questions of the 2^nd type: 3 + 3 = 6
25 * 
26 * <strong class="example">Example 2:
27 * 
28 * Input: target = 5, types = [[50,1],[50,2],[50,5]]
29 * Output: 4
30 * Explanation: You can earn 5 points in one of the four ways:
31 * - Solve 5 questions of the 0^th type: 1 + 1 + 1 + 1 + 1 = 5
32 * - Solve 3 questions of the 0^th type and 1 question of the 1^st type: 1 + 1 + 1 + 2 = 5
33 * - Solve 1 questions of the 0^th type and 2 questions of the 1^st type: 1 + 2 + 2 = 5
34 * - Solve 1 question of the 2^nd type: 5
35 * 
36 * <strong class="example">Example 3:
37 * 
38 * Input: target = 18, types = [[6,1],[3,2],[2,3]]
39 * Output: 1
40 * Explanation: You can only earn 18 points by answering all questions.
41 * 
42 *  
43 * Constraints:
44 * 
45 * 	1 <= target <= 1000
46 * 	n == types.length
47 * 	1 <= n <= 50
48 * 	types[i].length == 2
49 * 	1 <= counti, marksi <= 50
50 * 
51 */
52pub struct Solution {}
53
54// problem: https://leetcode.com/problems/number-of-ways-to-earn-points/
55// discuss: https://leetcode.com/problems/number-of-ways-to-earn-points/discuss/?currentPage=1&orderBy=most_votes&query=
56
57// submission codes start here
58
59impl Solution {
60    pub fn ways_to_reach_target(target: i32, types: Vec<Vec<i32>>) -> i32 {
61        0
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_2585() {
73    }
74}
75