把 n 个骰子扔在地上,求点数和为 s 的概率。
使用一个二维数组 dp 存储点数出现的次数,其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。
空间复杂度:O(N2)
class Solution {
public double[] twoSum(int n) {
// 1 1-6(1+5*n) 6^1
// 2 2-12 6^2
double all = Math.pow(6, n);
int[][] dp = new int[n+1][n*6+1];
// 状态数组
dp[0][0] = 1;
for(int i = 1; i <= n; i++) // i第几个色子
for(int j = i; j <= 6*n; j++) // j当前值的和
for(int k = 1; k <= 6 && k<=j; k++) // k代表当前筛子的值
// 状态转移方程:i个色子和为j += i-1个色子和 第i个色子值为k
dp[i][j] += dp[i-1][j-k];
double[] res = new double[1 + 5 * n];
for(int i = n; i <= n*6; i++)
res[i - n] = dp[n][i] / all;
return res;
}
}
空间复杂度:O(N)
public List<Map.Entry<Integer, Double>> dicesSum(int n) {
final int face = 6;
final int pointNum = face * n;
long[][] dp = new long[2][pointNum + 1];
for (int i = 1; i <= face; i++)
dp[0][i] = 1;
int flag = 1; /* 旋转标记 */
for (int i = 2; i <= n; i++, flag = 1 - flag) {
for (int j = 0; j <= pointNum; j++)
dp[flag][j] = 0; /* 旋转数组清零 */
for (int j = i; j <= pointNum; j++)
for (int k = 1; k <= face && k <= j; k++)
dp[flag][j] += dp[1 - flag][j - k];
}
final double totalNum = Math.pow(6, n);
List<Map.Entry<Integer, Double>> ret = new ArrayList<>();
for (int i = n; i <= pointNum; i++)
ret.add(new AbstractMap.SimpleEntry<>(i, dp[1 - flag][i] / totalNum));
return ret;
}