Leetcode2585. 获得分数的方法数

题解

多重背包的模板
f[i][j]表示前i种题目得分为j的方案数
f[i][j] += f[i-1][j-kw]
再将空间优化为1维

class Solution {
    public int waysToReachTarget(int target, int[][] types) {
        int n = types.length, MOD = (int) 1e9 + 7, INF = 0x3f3f3f3f;
        int[] f = new int[target + 1];
        f[0] = 1;
        for(int i = 0; i < n; i++){
            int s = types[i][0], w = types[i][1];
            for(int j = target; j >= w; j--){
                for(int k = 1; k <= s && k * w <= j; k++){
                    f[j] += f[j - k * w];
                    f[j] %= MOD;
                }
            }
        }
        return f[target];
    }
}