05 August 2008
掷骰子朝上的点数组成target的总数
记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
Integer[][] memo;
final int MOD = (int)1e9 + 7;
public int numRollsToTarget(int d, int f, int target) {
memo = new Integer[d + 1][target + 1];
return dfs(d, f, target);
}
int dfs(int d, int f, int target) {
if (d == 0 || target <= 0) return 0;
if (d == 1) return target <= f ? 1 : 0;
if (memo[d][target] != null) return memo[d][target];
int ans = 0;
for (int i = 1; i <= f; i++) {
ans = (ans + dfs(d - 1, f, target - i)) % MOD;
}
return memo[d][target] = ans;
}
}
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int numRollsToTarget(int d, int f, int target) {
final int MOD = (int)1e9 + 7;
int[][] dp = new int[d + 1][target + 1];
for (int i = 1; i <= target; i++) dp[1][i] = i <= f ? 1 : 0;
for (int i = 2; i <= d; i++) {
for (int j = 1; j <= target; j++) {
int ans = 0;
for (int k = 1; k <= f; k++) {
if (j - k >= 1) ans = (ans + dp[i - 1][j - k]) % MOD;
}
dp[i][j] = ans;
}
}
return dp[d][target];
}
}