2585. Number of Ways to Earn Points

Hard

273

8

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] = [count`

indicates that there are _{i}, marks_{i}]`count`

questions of the _{i}`i`

type, and each one of them is worth ^{th}`marks`

points._{i}

Return *the number of ways you can earn exactly *

`target`

`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 the`1`

and^{st}`2`

questions is the same as solving the^{nd}`1`

and^{st}`3`

questions, or the^{rd}`2`

and^{nd}`3`

questions.^{rd}

**Example 1:**

Input:target = 6, types = [[6,1],[3,2],[2,3]]Output:7Explanation: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:4Explanation: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:1Explanation: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

Accepted

9.3K

Submissions

15.5K

Acceptance Rate

59.8%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved