1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int numRollsToTarget(int n, int K, int target) {
const int mod = 1e9 + 7;
long long f[1005];
memset(f, 0, sizeof(f));
for (int i = 0; i < n; ++i) {
f[0] = i == 0 ? 1 : 0;
for (int j = 1; j <= target; ++j) f[j] = (f[j] + f[j - 1]) % mod;
for (int j = target; j >= 1; --j) {
f[j] = f[j - 1];
if (j - K - 1 >= 0) f[j] = (f[j] - f[j - K - 1] + mod) % mod;
}
}
return f[target];
}
};
|