Skip to content

2585. Number of Ways to Earn Points 👍

Approach 1: 2D DP

  • Time: $O(n \cdot \texttt{target} \cdot \texttt{count})$
  • Space: $O(n \cdot \texttt{target})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int waysToReachTarget(int target, vector<vector<int>>& types) {
    constexpr int kMod = 1'000'000'007;
    // dp[i][j] := the number of ways to earn j points with the first i types
    vector<vector<int>> dp(types.size() + 1, vector<int>(target + 1));
    dp[0][0] = 1;

    for (int i = 1; i <= types.size(); ++i) {
      const int count = types[i - 1][0];
      const int mark = types[i - 1][1];
      for (int j = 0; j <= target; ++j)
        for (int solved = 0; solved <= count; ++solved)
          if (j - solved * mark >= 0) {
            dp[i][j] += dp[i - 1][j - solved * mark];
            dp[i][j] %= kMod;
          }
    }

    return dp[types.size()][target];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int waysToReachTarget(int target, int[][] types) {
    final int kMod = 1_000_000_007;
    // dp[i][j] := the number of ways to earn j points with the first i types
    int[][] dp = new int[types.length + 1][target + 1];
    dp[0][0] = 1;

    for (int i = 1; i <= types.length; ++i) {
      final int count = types[i - 1][0];
      final int mark = types[i - 1][1];
      for (int j = 0; j <= target; ++j)
        for (int solved = 0; solved <= count; ++solved)
          if (j - solved * mark >= 0) {
            dp[i][j] += dp[i - 1][j - solved * mark];
            dp[i][j] %= kMod;
          }
    }

    return dp[types.length][target];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:
    kMod = 1_000_000_007
    # dp[i][j] := the number of ways to earn j points with the first i types
    dp = [[0] * (target + 1) for _ in range(len(types) + 1)]
    dp[0][0] = 1

    for i in range(1, len(types) + 1):
      count = types[i - 1][0]
      mark = types[i - 1][1]
      for j in range(target + 1):
        for solved in range(count + 1):
          if j - solved * mark >= 0:
            dp[i][j] += dp[i - 1][j - solved * mark]
            dp[i][j] %= kMod

    return dp[len(types)][target]

Approach 2: 1D DP

  • Time: $O(n \cdot \texttt{target} \cdot \texttt{count})$
  • Space: $O(\texttt{target})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int waysToReachTarget(int target, vector<vector<int>>& types) {
    constexpr int kMod = 1'000'000'007;
    // dp[j] := the number of ways to earn j points with the types so far
    vector<int> dp(target + 1);
    dp[0] = 1;

    for (const vector<int>& type : types) {
      const int count = type[0];
      const int mark = type[1];
      for (int j = target; j >= 0; --j)
        for (int solved = 1; solved <= count; ++solved)
          if (j - solved * mark >= 0) {
            dp[j] += dp[j - solved * mark];
            dp[j] %= kMod;
          }
    }

    return dp[target];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int waysToReachTarget(int target, int[][] types) {
    final int kMod = 1_000_000_007;
    // dp[j] := the number of ways to earn j points with the types so far
    int[] dp = new int[target + 1];
    dp[0] = 1;

    for (int[] type : types) {
      final int count = type[0];
      final int mark = type[1];
      for (int j = target; j >= 0; --j)
        for (int solved = 1; solved <= count; ++solved)
          if (j - solved * mark >= 0) {
            dp[j] += dp[j - solved * mark];
            dp[j] %= kMod;
          }
    }

    return dp[target];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:
    kMod = 1_000_000_007
    # dp[j] := the number of ways to earn j points with the types so far
    dp = [1] + [0] * target

    for count, mark in types:
      for j in range(target, -1, -1):
        for solved in range(1, count + 1):
          if j - solved * mark >= 0:
            dp[j] += dp[j - solved * mark]
            dp[j] %= kMod

    return dp[target]