#2585

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Ways to Earn Points

Find the number of ways to earn exactly target points using multiple types of exam questions with distinct marks.

Problem Statement

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 ith type, and each one of them is worth marksi 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.

Examples

Example 1

Input: target = 6, types = [[6,1],[3,2],[2,3]]

Output: 7

You can earn 6 points in one of the seven ways:

Solve 6 questions of the 0th type: 1 + 1 + 1 + 1 + 1 + 1 = 6
Solve 4 questions of the 0th type and 1 question of the 1st type: 1 + 1 + 1 + 1 + 2 = 6
Solve 2 questions of the 0th type and 2 questions of the 1st type: 1 + 1 + 2 + 2 = 6
Solve 3 questions of the 0th type and 1 question of the 2nd type: 1 + 1 + 1 + 3 = 6
Solve 1 question of the 0th type, 1 question of the 1st type and 1 question of the 2nd type: 1 + 2 + 3 = 6
Solve 3 questions of the 1st type: 2 + 2 + 2 = 6
Solve 2 questions of the 2nd type: 3 + 3 = 6

Example 2

Input: target = 5, types = [[50,1],[50,2],[50,5]]

Output: 4

You can earn 5 points in one of the four ways:

Solve 5 questions of the 0th type: 1 + 1 + 1 + 1 + 1 = 5
Solve 3 questions of the 0th type and 1 question of the 1st type: 1 + 1 + 1 + 2 = 5
Solve 1 questions of the 0th type and 2 questions of the 1st type: 1 + 2 + 2 = 5
Solve 1 question of the 2nd type: 5

Example 3

Input: target = 18, types = [[6,1],[3,2],[2,3]]

Output: 1

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 <= counti, marksi <= 50

Solution Approach

Dynamic Programming Approach

The problem can be solved using a state transition dynamic programming approach. Maintain a dp array where dp[i] represents the number of ways to achieve exactly 'i' points. For each question type, update the dp array considering all possible combinations of questions for that type.

State Transition for Each Question Type

For each question type, calculate the number of ways to form different scores using a number of questions from 0 to counti. Update the dp array accordingly by considering the impact of each question type's count and mark.

Modulo Operation

Since the number of ways can be large, perform modulo 10^9 + 7 to prevent overflow. This is crucial when dealing with large numbers in dynamic programming solutions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depends on the number of question types and the target value. The algorithm iterates over the target value and updates dp values for each question type, resulting in a time complexity of O(n * target), where n is the number of question types. Space complexity is O(target) for storing the dp array.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

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]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

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]

Continue Practicing

#2581 count number of possible root nodes #2573 find the string with lcp #2597 the number of beautiful subsets