Number of Ways to Earn Points

Problem Description

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_i, marks_i] indicates that there are count_i questions of the ith type, and each one of them is worth marks_i 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.

Key Insights

• The problem can be approached using dynamic programming to count combinations of questions that sum up to the target score.
• For each type of question, we can choose to answer between 0 and count_i questions, each contributing marks_i points.
• A DP array can be used where dp[j] represents the number of ways to earn exactly j points.

Space and Time Complexity

Time Complexity: O(n * target)
Space Complexity: O(target)

Solution

The problem can be solved using a dynamic programming approach. We maintain a DP array where each index represents the number of ways to achieve that score. For each question type, we iterate through the possible scores and update the DP array based on the number of questions and their respective marks.

1. Initialize a DP array of size target + 1 with dp[0] = 1 (one way to score zero points).
2. For each question type, iterate over the number of questions that can be taken and update the DP array for the scores that can be achieved with those questions.
3. Ensure to only count up to the maximum number of questions allowed for each type.

Code Solutions