题目描述
blablabla
样例
blablabla
算法1
(暴力枚举)
java 代码
static int[] res = null;
static int count;
public static int[] numberOfDice(int n) {
res = new int[6 * n - n + 1];
for (int i = n,j=0; i <= 6 * n; i++,j++) {
count = 0;
dfs(n, i);
res[j] = count;
}
return res;
}
private static void dfs(int n, int sum) {
if (sum == 0&&n==0) {
count++;
return;
}
if (n == 0)
return;
if (sum < 0)
return;
for (int i = 1; i <= 6; i++) {
dfs(n - 1, sum - i);
if (sum - i <= 0)
break;
}
}
算法2
(动态规划)
Java 代码
public int[] numberOfDice(int n) {
int[] res = new int[6 * n - n + 1];
int[][]f=new int[n+1][6*n+1];
f[0][0] = 1;
for(int i = 1; i <= n ; i++){
for(int j = 1; j <= i*6; j ++){
for(int k = 1; k <=Math.min(j, 6); k ++)
f[i][j] += f[i-1][j - k];
}
}
for (int i = n,j=0; i <= 6 * n; i++,j++) {
res[j] = f[n][i];
}
return res;
}