Question

2585. Number of Ways to Earn Points

中文文档

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] = [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

Solutions

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

We can enumerate the $i$th 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 $i$th 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.

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]

class Solution {
  public int waysToReachTarget(int target, int[][] types) {
    int n = types.length;
    final int mod = (int) 1e9 + 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];
  }
}

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];
  }
};

func waysToReachTarget(target int, types [][]int) int {
  n := len(types)
  f := make([][]int, n+1)
  for i := range f {
    f[i] = make([]int, target+1)
  }
  f[0][0] = 1
  const mod = 1e9 + 7
  for i := 1; i <= n; i++ {
    count, marks := types[i-1][0], types[i-1][1]
    for j := 0; j <= target; j++ {
      for 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]
}

function waysToReachTarget(target: number, types: number[][]): number {
  const n = types.length;
  const mod = 10 ** 9 + 7;
  const f: number[][] = Array.from({ length: n + 1 }, () => Array(target + 1).fill(0));
  f[0][0] = 1;
  for (let i = 1; i <= n; ++i) {
    const [count, marks] = types[i - 1];
    for (let j = 0; j <= target; ++j) {
      for (let 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];
}