Watch 10 video solutions for Number of Ways to Earn Points, a hard level problem involving Array, Dynamic Programming. This walkthrough by Aryan Mittal has 1,352 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 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 109 + 7.
Note that questions of the same type are indistinguishable.
3 questions of the same type, then solving the 1st and 2nd questions is the same as solving the 1st and 3rd questions, or the 2nd and 3rd 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 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 Explanation: 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 Explanation: You can only earn 18 points by answering all questions.
Constraints:
1 <= target <= 1000n == types.length1 <= n <= 50types[i].length == 21 <= counti, marksi <= 50Problem Overview: You are given several question types where each type provides a fixed number of points and can be used a limited number of times. The goal is to count how many different combinations of questions reach exactly the target score. Order does not matter, so this becomes a bounded combination counting problem.
Approach 1: Recursive Dynamic Programming with Memoization (Time: O(n * target * count), Space: O(n * target))
Treat the problem as a decision process across question types. At index i, decide how many questions of the current type to take (from 0 to count[i]). Each choice subtracts k * marks[i] from the remaining score and recursively processes the next type. Without caching, this creates many repeated subproblems. Memoization stores results for states defined by (index, remainingScore). This converts the exponential recursion into a polynomial solution. The approach is intuitive and mirrors the combinational search directly, which helps when reasoning about constraints and correctness.
This solution relies heavily on overlapping subproblems and is a classic application of dynamic programming. The input structure is stored in an array of types, and recursion iterates through each type while tracking the remaining score.
Approach 2: Dynamic Programming with State Compression (Bounded Knapsack) (Time: O(n * target * count), Space: O(target))
This problem maps directly to the bounded knapsack counting pattern. Let dp[s] represent the number of ways to reach score s. Initialize dp[0] = 1. For each question type, iterate scores from target down to 0. For every possible number of questions k from 1 to the allowed count, update dp[s] using dp[s - k * marks] if the score remains valid.
Iterating scores backward prevents reuse of the same question type more times than allowed. This effectively compresses the 2D DP state (type, score) into a single dimension. The memory usage drops to O(target), which is efficient for the constraint where the target score can be up to around 1000.
Recommended for interviews: The state-compressed dynamic programming solution is what interviewers typically expect. It demonstrates recognition of the bounded knapsack pattern and efficient space optimization. The recursive memoized version is still valuable during explanation because it clearly shows the decision structure before converting it into iterative DP.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DP with Memoization | O(n * target * count) | O(n * target) | When reasoning about the problem recursively or explaining the state transition during interviews |
| Dynamic Programming with State Compression (Bounded Knapsack) | O(n * target * count) | O(target) | Preferred production and interview solution due to lower memory usage and clean iterative implementation |