2585

2585. Number of Ways to Earn Points (Hard)

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

Companies: TuSimple

Related Topics:
Array, Dynamic Programming

Similar Questions:

• Coin Change II (Medium)
• Minimum Total Distance Traveled (Hard)

Hints:

• Use Dynamic Programming
• Let ways[i][points] be the number of ways to score a given number of points after solving some questions of the first i types.
• ways[i][points] is equal to the sum of ways[i-1][points - solved * marks[i] over 0 <= solved <= count_i

Solution 1. Bounded Knapsack

Let dp[i+1][k] be the number of way to get k points with A[0..i]. The answer is dp[N][K].

dp[i+1][0] = 1

dp[i+1][k] = dp[i][k]  // don't use i-th question
             dp[i][k - A[i][1]] // use 1 i-th question
             dp[i][k - 2 * A[i][1]] // use 2 i-th questions
             ...
dp[i+1][k] = sum( dp[i][k - t * A[i][1]] | 0 <= t <= A[i][0] AND k - t * A[i][1] >= 0 )

// OJ: https://leetcode.com/problems/number-of-ways-to-earn-points
// Author: github.com/lzl124631x
// Time: O(NK^2)
// Space: O(NK)
class Solution {
public:
    int waysToReachTarget(int K, vector<vector<int>>& A) {
        int N = A.size(), dp[51][1001] = {}, mod = 1e9 + 7;
        dp[0][0] = 1;
        for (int i = 0; i < N; ++i) {
            for (int k = 0; k <= K; ++k) {
                for (int t = 0; t <= A[i][0] && k - t * A[i][1] >= 0; ++t) {
                    dp[i + 1][k] = (dp[i + 1][k] + dp[i][k - t * A[i][1]]) % mod;
                }
            }
        }
        return dp[N][K];
    }
};

Solution 2. DP with Space Optimization

// OJ: https://leetcode.com/problems/number-of-ways-to-earn-points
// Author: github.com/lzl124631x
// Time: O(NK^2)
// Space: O(K)
class Solution {
public:
    int waysToReachTarget(int K, vector<vector<int>>& A) {
        int N = A.size(), dp[1001] = {}, mod = 1e9 + 7;
        dp[0] = 1;
        for (int i = 0; i < N; ++i) {
            int next[1001] = {};
            for (int k = 0; k <= K; ++k) {
                for (int t = 0; t <= A[i][0] && k - t * A[i][1] >= 0; ++t) {
                    next[k] = (next[k] + dp[k - t * A[i][1]]) % mod;
                }
            }
            swap(dp, next);
        }
        return dp[K];
    }
};

Or

// OJ: https://leetcode.com/problems/number-of-ways-to-earn-points
// Author: github.com/lzl124631x
// Time: O(NK)
// Space: O(K)
class Solution {
public:
    int waysToReachTarget(int target, vector<vector<int>>& A) {
        int dp[1001] = {[0] = 1}, mod = 1e9 + 7;
        for (auto &v : A) {
            int cnt = v[0], mark = v[1], next[1001] = {}, sum[51] = {};
            for (int t = 0; t <= target; ++t) {
                int i = t % mark;
                sum[i] = (sum[i] + dp[t]) % mod;
                if (t - (cnt + 1) * mark >= 0) sum[i] = (sum[i] - dp[t - (cnt + 1) * mark] + mod) % mod;
                next[t] = sum[i];
            }
            swap(next, dp);
        }
        return dp[target];
    }
};