1、题目描述
将一个骰子投掷n次,获得的总点数为s,s的可能范围为n~6n。
掷出某一点数,可能有多种掷法,例如投掷2次,掷出3点,共有[1,2],[2,1]两种掷法。
请求出投掷n次,掷出n~6n点分别有多少种掷法。
样例
输入:n=1
输出:[1, 1, 1, 1, 1, 1]
解释:投掷1次,可能出现的点数为1-6,共计6种。每种点数都只有1种掷法。所以输出[1, 1, 1, 1, 1, 1]。
输入:n=2
输出:[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
解释:投掷2次,可能出现的点数为2-12,共计11种。每种点数可能掷法数目分别为1,2,3,4,5,6,5,4,3,2,1。
所以输出[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]。
Java代码
class Solution {
public int[] numberOfDice(int n) {
/*
动态规划:dp[i][j] 表示前i次总和是j的掷法数
当第i次掷出的点数是k时,dp[i][j]=dp[i-1][j-k];
因为k的取值为1-6,所以此时dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+..+dp[i-1][j-k]
注意这里是有条件的就是j>=k+1 因为i是从2开始,说明至少掷两次,加入j=6 k=6 不可能掷两次
*/
int[][] dp=new int[n+1][6*n+1];
for(int i=1;i<=6;i++){
dp[1][i]=1;
}
for(int i=2;i<=n;i++){
for(int j=i;j<=i*6;j++){
for(int k=1;k<=6;k++){
if(j<k+1){
continue;
}
dp[i][j]+=dp[i-1][j-k];
}
}
}
int[] res=new int[6*n-n+1];
for(int i=0;i<res.length;i++){
res[i]=dp[n][i+n];
}
return res;
}
}
2、题目描述
把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
样例
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
Java代码
class Solution {
public double[] dicesProbability(int n) {
double[][] dp=new double[n+1][n*6+1];
//dp[i][j]表示i个骰子投掷出总和为j的概率之和
//如果第i个骰子投掷出的点数为k dp[i][j]=dp[1][k]*dp[i-1][j-k]
//k=1————6 dp[i][j]=dp[1][1]*dp[i-1][j-1]+dp[1][2]*dp[i-1][j-2]+..+dp[1][k]*dp[i-1][j-k]
for(int i=1;i<=6;i++){
dp[1][i]=(double)1/6;
}
for(int i=2;i<=n;i++){
for(int j=i;j<=6*n;j++){
for(int k=1;k<=6;k++){
if(j<k+1) continue;
dp[i][j]+=dp[1][k]*dp[i-1][j-k];
}
}
}
double[] res=new double[5*n+1];
for(int i=0;i<res.length;i++){
res[i]=dp[n][i+n];
}
return res;
}
}
j>=k+1 想了好一会,其实写成j-k>=1就理解了