JZ-074-n 个骰子的点数
n 个骰子的点数 题目描述
把 n 个骰子仍在地上,求点数和为 s 的概率。代码
【JZ-074-n 个骰子的点数】题目链接: [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 <= face;
i++)
dp[1][i] = 1;
for (int i = 2;
i <= n;
i++)
for (int j = i;
j <= pointNum;
j++)/* 使用 i 个骰子最小点数为 i */
for (int k = 1;
k <= face && k <= j;
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 <= pointNum;
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 <= 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> ret = new ArrayList<>();
for (int i = n;
i <= pointNum;
i++)
ret.add(new AbstractMap.SimpleEntry<>(i, dp[1 - flag][i] / totalNum));
return ret;
}public static void main(String[] args) {}
}
【每日寄语】 香九龄,能温席;孝于亲,所当执。
推荐阅读
- Vite 实战(手把手教你写一个 Vite 插件)
- 两个半月零事故割接!我爱我家全业务顺利迁移华为云
- 腾讯云开源业界首个云原生标准的一站式微服务管理框架Femas
- vue实现文字展开收起功能
- win如何用防火墙禁用某个软件联网
- react|react 递归遍历四层树结构 遍历分支中的最后一个节点_图解(数据结构中的 6 种树,你心中有数吗(...))
- 牛客网刷题笔记【1】
- 刚面完字节跳动,估计凉了。
- 如何使用|如何使用 Cordova 将 SAP UI5 应用生成一个能在 Android 手机上安装的混合应用试读版
- 业界首个!腾讯云原生一站式微服务管理框架 Femas 正式开源