welcome to my blog
剑指offer 面试题60(java版):n个骰子的点数
题目描述
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
class Solution {
public double[] twoSum(int n) {
int low=n, up=6*n;
double[] res = new double[up-low+1];
double denominator = Math.pow(6,n);
// f(n,s)表示n个骰子的和为s时出现的次数
//f(n, s) = f(n-1, s-1) + f(n-1, s-2) +f(n-1, s-3) +f(n-1, s-4) +f(n-1, s-5) +f(n-1, s-6)
int[][] dp = new int[n+1][up+1];
for(int j=1; j<=6; j++){
dp[1][j] = 1;
}
for(int i=2; i<=n; i++){
for(int j=i; j<=6*i; j++){
//一定要保证j-k>=1
for(int k=1; k<=6 && j-k>=1; k++){
dp[i][j] += dp[i-1][j-k];
}
}
}
for(int i=0; i<res.length; i++){
res[i] = dp[n][n+i] / denominator;
}
return res;
}
}class Solution {
public double[] twoSum(int n) {
int low=n, up=6*n;
double[] res = new double[up-low+1];
double denominator = Math.pow(6,n);
core(res, n, 0, 0);
for(int i=0; i<res.length; i++){
res[i] = res[i]/denominator;
}
return res;
}
private void core(double[] res, int n, int index, int sum){
//base case
if(index==n){
res[sum-n]++;
return;
}
//
for(int i=1; i<=6; i++){
core(res, n, index+1, sum+i);
}
}
}第一次做; 状态压缩版本的动态规划; 还是得看着下面的矩阵图写, 否则容易乱
/*
动态规划
设F(n,s)表示n个骰子的和为s的出现次数
F(n,s) = F(n-1, s-1) + F(n-1, s-2) + F(n-1, s-3) + F(n-1, s-4) + F(n-1, s-5) + F(n-1, s-6)
*/
class Solution {
public double[] twoSum(int n) {
int[][] dp = new int[2][6*n+1];
int cur = 0;
for(int j=1; j<=6; j++){
dp[cur][j] = 1;
}
for(int i=2; i<=n; i++){
//初始化dp[1-cur]这个骰子
Arrays.fill(dp[1-cur], 0);
for(int j=i; j<=6*i; j++){
for(int k=1; k<=6 & j-k>=1; k++){
dp[1-cur][j] += dp[cur][j-k];
}
}
//交换
cur = 1 - cur;
}
double denominator = Math.pow(6,n);
int which = n%2==1? 0 : 1;
double[] res = new double[6*n-n+1];
int index=0;
for(int j=n; j<=6*n; j++){
res[index++] = dp[which][j]/denominator;
}
return res;
}
}
第一次做; 动态规划, 核心: 1)递归公式: 设F(n,s)表示n个骰子的和为s的出现次数, 那么n个骰子和n-1个骰子之间的关系满足: F(n,s) = F(n-1, s-1) + F(n-1, s-2) + F(n-1, s-3) + F(n-1, s-4) + F(n-1, s-5) + F(n-1, s-6); 如下图所示, 矩阵中某个位置的元素是上一行中某六个连续的元素有关; 2) dp[i][j]表示i个骰子和为j时的出现次数; 可以发现dp[i][j]只依赖于上一行的元素, 所以可以进行状态压缩
/*
动态规划
设F(n,s)表示n个骰子的和为s的出现次数
F(n,s) = F(n-1, s-1) + F(n-1, s-2) + F(n-1, s-3) + F(n-1, s-4) + F(n-1, s-5) + F(n-1, s-6)
*/
class Solution {
public double[] twoSum(int n) {
int[][] dp = new int[n+1][6*n+1];
//初始化第1行
for(int j=1; j<=6; j++){
dp[1][j] = 1;
}
for(int i=2; i<=n; i++){
for(int j=i; j<=6*i; j++){
for(int k=1; k<=6 && j-k>=1; k++){
dp[i][j] += dp[i-1][j-k];
}
}
}
double[] res = new double[6*n-n+1];
int index=0;
double denominator = Math.pow(6,n);
for(int j=n; j<=6*n; j++){
res[index++] = dp[n][j]/denominator;
}
return res;
}
}
第一次做; 使用递归函数模拟n个筛子的全排列, 记录每种组合出现的次数; 细节: Math.pow()的返回值是double
/*
n个骰子, 最小值是n, 最大值是6n
*/
class Solution {
public double[] twoSum(int n) {
double[] res = new double[6*n-n+1];
core(res,n,0,0);
double denominator = Math.pow(6,n);
for(int i=0; i<res.length; i++){
res[i] = res[i]/denominator;
}
return res;
}
//全排列(使用递归实现很方便)
//递归函数逻辑: 求当前骰子的点数 加上 剩余骰子的点数和
private void core(double[] res, int n, int index, int sum){
//base case
if(index==n){
res[sum-n]++;
return;
}
//
for(int i=1; i<=6; i++){
core(res, n, index+1, sum+i);
}
}
}
力扣优秀题解
