题解
多重背包的模板
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];
}
}