# Number of Ways to Earn Points
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-ways-to-earn-points)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-earn-points
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [TuSimple](https://scaleengineer.com/companies/tusimple)
---
## Problem
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`

# Approaches
## Brute-Force Dynamic Programming
This is a fundamental dynamic programming approach that directly models the problem. We use a 2D array, `dp[i][j]`, to store the number of ways to achieve a score of `j` using the first `i` types of questions. The solution iterates through each question type and, for each type, considers all possible numbers of questions to solve (from 0 to `count_i`), summing up the ways from the previous state.
**Time:** O(n * target * max_count), where `n` is the number of types, `target` is the target score, and `max_count` is the maximum count for any question type. This is due to three nested loops. · **Space:** O(n * target) for the 2D DP table.
**Pros:** Intuitive and directly follows the problem's combinatorial nature.
**Cons:** The time complexity is high due to the third nested loop.; Space complexity can be large for high `n` and `target`.
### Explanation
We define a DP state `dp[i][j]` which represents the number of ways to earn exactly `j` points using the first `i` types of questions (from index 0 to `i-1`). The state transition is formulated by considering the `i`-th question type, which has `count = types[i-1][0]` questions, each worth `marks = types[i-1][1]` points. To calculate `dp[i][j]`, we can solve `k` questions of this type, where `0 <= k <= count`. The points earned would be `k * marks`. The remaining `j - k * marks` points must be formed using the first `i-1` types, for which there are `dp[i-1][j - k * marks]` ways. The recurrence relation is: `dp[i][j] = Σ (from k=0 to count) dp[i-1][j - k * marks]`. The base case is `dp[0][0] = 1`, signifying one way to get a score of 0 with zero question types (by solving none). We build the `dp` table of size `(n+1) x (target+1)` bottom-up. The final answer is stored in `dp[n][target]`. The modulo operation is applied at each addition to prevent overflow.
```java
class Solution {
    public int waysToReachTarget(int target, int[][] types) {
        int n = types.length;
        int MOD = 1_000_000_007;
        int[][] dp = new int[n + 1][target + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            int count = types[i - 1][0];
            int marks = types[i - 1][1];
            for (int j = 0; j <= target; j++) {
                for (int k = 0; k <= count; k++) {
                    if (j >= k * marks) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - k * marks]) % MOD;
                    }
                }
            }
        }
        return dp[n][target];
    }
}
```
### Algorithm
- Create a 2D DP table `dp` of size `(n + 1) x (target + 1)` and initialize it to 0.
- Set `dp[0][0] = 1`.
- Loop through each question type `i` from 1 to `n`.
- For each type, get its `count` and `marks`.
- Loop through each possible target score `j` from 0 to `target`.
- Loop through the number of questions `k` to solve for the current type, from 0 to `count`.
- If the current score `j` is sufficient (`j >= k * marks`), add the ways from the previous state `dp[i-1][j - k * marks]` to `dp[i][j]`.
- Apply modulo at each addition.
- The result is `dp[n][target]`.

## Space-Optimized Brute-Force DP
This approach refines the brute-force DP by reducing its space complexity. Observing that the calculation for the current question type `i` only depends on the results from the immediately preceding type `i-1`, we can avoid storing the entire 2D DP table. Instead, we use only two 1D arrays: one for the previous state and one for the current state.
**Time:** O(n * target * max_count). The time complexity is not improved, as the three nested loops structure is maintained. · **Space:** O(target), as we only need two arrays of size `target + 1` to store DP states.
**Pros:** Significantly reduces memory usage, making it feasible for problems with larger `n` or `target` where memory might be a constraint.
**Cons:** The time complexity remains the bottleneck, identical to the non-space-optimized version.
### Explanation
Instead of a `(n+1) x (target+1)` table, we use two 1D arrays, `dp` and `new_dp`, both of size `target+1`. `dp` stores the results for the previous type, and `new_dp` is used to compute the results for the current type. We initialize `dp[0] = 1` and all other elements of `dp` to 0. We iterate through each question type. In each iteration, we calculate `new_dp` based on the values in `dp`. The update rule remains the same: `new_dp[j] = Σ (from k=0 to count) dp[j - k * marks]`. After processing all scores `j` for the current type, the `new_dp` array holds the complete results for this stage. We then assign `new_dp` to `dp` to prepare for the next question type. This cycle of computing `new_dp` from `dp` and then updating `dp` continues for all question types.
```java
class Solution {
    public int waysToReachTarget(int target, int[][] types) {
        int n = types.length;
        int MOD = 1_000_000_007;
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 0; i < n; i++) {
            int count = types[i][0];
            int marks = types[i][1];
            int[] new_dp = new int[target + 1];
            for (int j = 0; j <= target; j++) {
                for (int k = 0; k <= count; k++) {
                    if (j >= k * marks) {
                        new_dp[j] = (new_dp[j] + dp[j - k * marks]) % MOD;
                    }
                }
            }
            dp = new_dp;
        }
        return dp[target];
    }
}
```
### Algorithm
- Initialize a 1D array `dp` of size `target + 1`, with `dp[0] = 1`.
- Loop through each question type `i` from 0 to `n-1`.
- Create a temporary array `new_dp` of size `target + 1`, initialized to 0.
- Get `count` and `marks` for type `i`.
- Loop through each score `j` from 0 to `target`.
- Loop through `k` from 0 to `count`.
- If `j >= k * marks`, update `new_dp[j]` by adding `dp[j - k * marks]`.
- After the inner loops, assign `new_dp` to `dp`.
- The final answer is `dp[target]`.

## Optimized Dynamic Programming
This is the most efficient solution, which improves the time complexity by eliminating the innermost loop of the brute-force DP. The summation `Σ dp[j - k * marks]` is recognized as a form of sliding window sum, which can be computed in O(1) time for each state by using a clever recurrence relation.
**Time:** O(n * target). The innermost loop is removed, leading to a quadratic time complexity which is a significant improvement. · **Space:** O(target). Similar to the previous approach, it uses two 1D arrays for the DP states.
**Pros:** Highly efficient time complexity.; Optimal space complexity.
**Cons:** The recurrence relation is less intuitive and harder to derive than the brute-force approach.
### Explanation
This approach also uses a 1D DP array `dp` that is updated for each question type. Let `dp_prev` be the DP array before considering the current type and `dp_curr` be the array after. The core recurrence `dp_curr[j] = Σ (from k=0 to count) dp_prev[j - k * marks]` is optimized. We can establish a relationship: `dp_curr[j] = dp_prev[j] + dp_curr[j - marks] - dp_prev[j - (count + 1) * marks]`. Let's break down this formula:
- `dp_prev[j]`: This is the number of ways to get score `j` without using the current question type at all (i.e., solving 0 questions of this type).
- `dp_curr[j - marks]`: This term represents the number of ways to get score `j-marks` using the types up to the current one. It cleverly accumulates the sums for us. It represents `Σ (from k=0 to count) dp_prev[j - marks - k * marks]`.
- `dp_prev[j - (count + 1) * marks]`: The `dp_curr[j - marks]` term effectively assumes we can take an unlimited number of questions of the current type. We must subtract the cases where we take more than `count` questions. This term removes the ways corresponding to taking `count + 1` or more questions. By iterating `j` from 0 to `target`, we can compute `dp_curr` using `dp_prev` and previously computed values of `dp_curr` in O(1) per state.
```java
class Solution {
    public int waysToReachTarget(int target, int[][] types) {
        int n = types.length;
        int MOD = 1_000_000_007;
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int[] type : types) {
            int count = type[0];
            int marks = type[1];
            int[] new_dp = new int[target + 1];
            for (int j = 0; j <= target; j++) {
                // Ways from previous types (solving 0 of current type)
                long ways = dp[j];
                
                // Ways by solving at least one of current type (cumulative sum)
                if (j >= marks) {
                    ways = (ways + new_dp[j - marks]) % MOD;
                }
                
                // Remove overcounted cases (where > count questions were taken)
                if (j >= (count + 1) * marks) {
                    ways = (ways - dp[j - (count + 1) * marks] + MOD) % MOD;
                }
                new_dp[j] = (int) ways;
            }
            dp = new_dp;
        }
        return dp[target];
    }
}
```
### Algorithm
- Initialize a 1D array `dp` of size `target + 1`, with `dp[0] = 1`.
- Loop through each question type `(count, marks)`.
- Create a temporary array `new_dp` of size `target + 1`.
- Loop through each score `j` from 0 to `target`.
- Calculate `new_dp[j]` using the optimized recurrence:
    - `ways = dp[j]` (ways from previous types).
    - If `j >= marks`, add `new_dp[j - marks]` to `ways`.
    - If `j >= (count + 1) * marks`, subtract `dp[j - (count + 1) * marks]` from `ways`.
    - Remember to handle modulo and potential negative results.
    - Store the result in `new_dp[j]`.
- After the inner loop, assign `new_dp` to `dp`.
- The final answer is `dp[target]`.

# Solutions
### Java

```java
class Solution {
public
  int waysToReachTarget(int target, int[][] types) {
    int n = types.length;
    final int mod = (int)1 e9 + 7;
    int[][] f = new int[n + 1][target + 1];
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      int count = types[i - 1][0], marks = types[i - 1][1];
      for (int j = 0; j <= target; ++j) {
        for (int k = 0; k <= count; ++k) {
          if (j >= k * marks) {
            f[i][j] = (f[i][j] + f[i - 1][j - k * marks]) % mod;
          }
        }
      }
    }
    return f[n][target];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int waysToReachTarget(int target, vector<vector<int>> &types) {
    int n = types.size();
    const int mod = 1e9 + 7;
    int f[n + 1][target + 1];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      int count = types[i - 1][0], marks = types[i - 1][1];
      for (int j = 0; j <= target; ++j) {
        for (int k = 0; k <= count; ++k) {
          if (j >= k * marks) {
            f[i][j] = (f[i][j] + f[i - 1][j - k * marks]) % mod;
          }
        }
      }
    }
    return f[n][target];
  }
};

```

### Python

```python
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]

```