Skip to main content
Talentd

Number of Ways to Earn Points - Solution & Explanation

HardArrayDynamic Programming20 min readAsked at: TuSimple
Practice this problem

Problem Statement

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.

  • For example, if there are 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 <= 1000
  • n == types.length
  • 1 <= n <= 50
  • types[i].length == 2
  • 1 <= counti, marksi <= 50

Approach Overview

Problem 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 1: Dynamic Programming with State Compression

This approach uses a dynamic programming (DP) technique to determine the number of different ways to achieve the target score. We use a 1D DP array where dp[j] represents the number of ways to achieve a score of j.

  1. Initialize an array dp with dp[0] set to 1 (one way to score zero points) and the rest to 0.
  2. Iterate through each type of question, updating the DP array based on the number of questions of that type and the points they contribute.
  3. For each multiple of the mark for that type, adjust the scores up to the target.

This approach uses state compression to keep the memory usage low by maintaining only scores that are still reachable given the constraints.

The C implementation initializes a dp array of size target + 1, filled initially with zeroes and sets dp[0] to 1, representing one way to achieve a score of zero by not solving any questions.

The nested loops iterate through each question type and update the possible scores in the dp array, considering the number of each type of question and their respective scores.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * target * countmax)
Space Complexity: O(target), where countmax is the maximum count of questions of any type.

Try this approach in the editor →

Approach 2: Recursive Dynamic Programming with Memoization

This approach utilizes recursion with memoization to explore all possible combinations of question types to achieve the target score. Each recursive call evaluates if it's possible to achieve the remaining score using the current and subsequent question types. Memoization is used to store results of subproblems to avoid re-computation.

  1. Define a recursive function to traverse each type of question and attempt to reach the target score.
  2. Use memoization to store the results of subproblems (e.g., how many ways to achieve a specific remaining score using given question types).
  3. Iteratively consider solving each number of questions of the current type.

In this Python solution, recursion with memoization is used to explore different scores. The dp() function considers each possible number of questions of a current type and recursively attempts to reach the target by calling itself with a decreased target and incremented index. Memoization efficiently caches computed results for quicker access.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n * target * countmax) in the worst case, due to solving subproblems.
Space Complexity: O(n * target) due to recursion and memoization storage.

Try this approach in the editor →

Approach 3: 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 ith 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[i-1][j-k times marks]

where k represents the number of questions of the ith 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with State Compression

Time Complexity: O(n * target * countmax)
Space Complexity: O(target), where countmax is the maximum count of questions of any type.

Recursive Dynamic Programming with Memoization

Time Complexity: O(n * target * countmax) in the worst case, due to solving subproblems.
Space Complexity: O(n * target) due to recursion and memoization storage.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive DP with MemoizationO(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

Video Solution

Number of Ways to Earn Points || Dynamic Programming Knapsack || Leetcode-2585 • Aryan Mittal • 1,451 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Ways to Earn Points easy or hard?
Number of Ways to Earn Points is classified as a Hard problem because it combines bounded knapsack with combination counting. The challenge comes from handling limited quantities while avoiding overcounting and optimizing the DP state to keep memory manageable.
Number of Ways to Earn Points Python or Java solution
Both Python and Java implementations typically use the same bounded knapsack DP logic. A 1D array dp[target + 1] is updated for each question type while iterating scores backward. The algorithm remains O(n * target * count) with O(target) memory regardless of language.
What is the best approach for Number of Ways to Earn Points?
The most efficient approach is dynamic programming using the bounded knapsack pattern. Maintain a 1D DP array where dp[s] stores the number of ways to achieve score s. For each question type, iterate the target score backward and try taking the question 0 to count times. This runs in O(n * target * count) time and O(target) space.
Is Number of Ways to Earn Points asked at Google/Amazon/Meta?
Dynamic programming and knapsack-style counting problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of bounded knapsack, DP state transitions, and optimization using 1D state compression.
What data structure is used in Number of Ways to Earn Points?
The core data structure is a dynamic programming array. The question types are stored in an array where each entry contains the number of available questions and the points earned. The DP array tracks how many ways each score can be achieved.
What is the time complexity of Number of Ways to Earn Points?
The typical dynamic programming solution runs in O(n * target * count) time, where n is the number of question types and count is the maximum allowed usage per type. Each type iterates through the target score and tries all allowed quantities. Space complexity can be reduced to O(target) using state compression.
How to solve Number of Ways to Earn Points in O(n * target * count)?
Use a bounded knapsack dynamic programming approach. Initialize dp[0] = 1 and process each question type one by one. For every score from target down to 0, add contributions from using 1..count questions of that type. This counts all valid combinations without exceeding the allowed usage.

Ready to solve this problem?

Practice Number of Ways to Earn Points with our built-in code editor and test cases.

Practice on FleetCode
Previous

Coin Change II

Next

Minimum Total Distance Traveled