n 个骰子的点数

题目描述

把 n 个骰子仍在地上，求点数和为 s 的概率。

题目链接: n 个骰子的点数

代码

import java.util.AbstractMap;

import java.util.ArrayList;

import java.util.List;

import java.util.Map;

/**

* 标题：n 个骰子的点数

* 把 n 个骰仍在在地上，求点数和为 s 的概率。

*/

public class Jz74 {

/**

* 动态规划

* 使用一个二维数组 dp 存储点数出现的次数，其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。

* 空间复杂度：O(N2)

*

* @param

* @return

*/

public List dicesSum(int n) {

final int face = 6;

final int pointNum = face * n;

long[][] dp = new long[n + 1][pointNum + 1];

for (int i = 1; i

dp[1][i] = 1;

for (int i = 2; i

for (int j = i; j

for (int k = 1; k

dp[i][j] += dp[i - 1][j - k];

final double totalNum = Math.pow(6, n);

List ret = new ArrayList();

for (int i = n; i

ret.add(new AbstractMap.SimpleEntry(i, dp[n][i] / totalNum));

return ret;

}

/**

* 动态规划 + 旋转数组

* 空间复杂度：O(N)

*

* @param n

* @return

*/

public List dicesSum2(int n) {

final int face = 6;

final int pointNum = face * n;

long[][] dp = new long[2][pointNum + 1];

for (int i = 1; i

dp[0][i] = 1;

int flag = 1; /* 旋转标记 */

for (int i = 2; i

for (int j = 0; j

dp[flag][j] = 0; /* 旋转数组清零 */

for (int j = i; j

for (int k = 1; k

dp[flag][j] += dp[1 - flag][j - k];

}

final double totalNum = Math.pow(6, n);

List ret = new ArrayList();

for (int i = n; i

ret.add(new AbstractMap.SimpleEntry(i, dp[1 - flag][i] / totalNum));

return ret;

}

public static void main(String[] args) {

}

}

【每日寄语】 香九龄，能温席；孝于亲，所当执。

关键词： JZ-074-n 个骰子的点数 java 动态规划 final