获得分数的方法数

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

/*
题目思路：
使用Java Stream API来实现动态规划。我们依然定义dp数组用于存储达到各分数的方案数。
通过Stream来进行数组的迭代和更新。
*/

import java.util.*;
import java.util.stream.IntStream;

public class Solution {
    public int numOfWays(int target, int[][] types) {
        int MOD = 1000000007;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int[] type : types) {
            int count = type[0];
            int marks = type[1];
            int[] newDp = Arrays.copyOf(dp, dp.length);
            IntStream.range(0, target + 1).forEach(i -> {
                IntStream.rangeClosed(1, count).forEach(k -> {
                    if (i + k * marks <= target) {
                        newDp[i + k * marks] = (newDp[i + k * marks] + dp[i]) % MOD;
                    }
                });
            });
            dp = newDp;
        }
        return dp[target];
    }
}

本题解使用动态规划来解决这个问题。我们定义 dp[i][j] 为考虑到第 i 种类型的题目时，恰好得到 j 分的方法数。初始状态 dp[0][0] = 1，意味着不选择任何题目时，得分为 0 的方法有一种。对于每种类型的题目，我们更新 dp 数组，计算使用这种类型的题目可以获得的不同分数的方法数。对于每种类型的题目 types[i] = [counti, marksi]，我们需要处理可选数量和分值情况，利用前缀和思想优化计算过程，防止重复计算。最终，dp[n][target] 将给出恰好得到 target 分的方法数。

O(n*target)

O(n*target)