🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯
题目链接
剑指 Offer 60. 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]
限制:
1 <= n <= 11
求解思路&实现代码&运行结果
暴力递归
求解思路
- 为了能够让同学们更好的理解这个过程,我特意将整个思考的过程以及作图的过程都绘制在下面这张图中,希望可以通过下面这张图更好的帮助你理解整个过程,大家可以结合这张图来理解整个题目的求解思路。
实现代码
class Solution {
private int n;
List<Double> list;
public double[] dicesProbability(int n) {
this.n=n;
list=new ArrayList<>();
int start=n,end=n*6;
process(start,end,n);
double[] ans=new double[list.size()];
for(int i=0;i<list.size();i++){
ans[i]=list.get(i);
}
return ans;
}
public void process(int start,int end,int cnt){
for(int i=start;i<=end;i++){
int count=dfs(i,cnt);
list.add(1.0/Math.pow(6,n)*count);
}
}
public int dfs(int target,int cnt){
if(cnt==0) return target==0?1:0;
int count=0;
for(int i=1;i<=6;i++){
count+=dfs(target-i,cnt-1);
}
return count;
}
}
运行结果
记忆化搜索
求解思路
- 根据我们递归的分析,在递归的过程中会产生重复的子过程,所以我们想到了加一个缓存表,也就是我们的记忆化搜索。
实现代码
class Solution {
private int n;
private List<Double> list;
public double[] dicesProbability(int n) {
this.n=n;
list=new ArrayList<>();
int start=n,end=n*6;
process(start,end,n);
double[] ans=new double[list.size()];
for(int i=0;i<list.size();i++){
ans[i]=list.get(i);
}
return ans;
}
public void process(int start,int end,int cnt){
int[][] dp=new int[12*6][12];
for(int i=0;i<dp.length;i++) Arrays.fill(dp[i],-1);
for(int i=start;i<=end;i++){
int count=dfs(i,cnt,dp);
list.add(1.0/Math.pow(6,n)*count);
}
}
public int dfs(int target,int cnt,int[][] dp){
if(target<0) return 0;
if(cnt==0) return dp[target][cnt]=target==0?1:0;
if(dp[target][cnt]!=-1) return dp[target][cnt];
int count=0;
for(int i=1;i<=6;i++){
count+=dfs(target-i,cnt-1,dp);
}
return dp[target][cnt]=count;
}
}
运行结果
动态规划
求解思路
- 接下来我们根据之前的递归思路以及记忆化缓存改写动态规划。
实现代码
class Solution {
private int n;
private List<Double> list;
public double[] dicesProbability(int n) {
this.n=n;
list=new ArrayList<>();
int start=n,end=n*6;
process(start,end,n);
double[] ans=new double[list.size()];
for(int i=0;i<list.size();i++){
ans[i]=list.get(i);
}
return ans;
}
public void process(int start,int end,int cnt){
int[][] dp=new int[12*6][12];
dp[0][0]=1;
for(int target=1;target<=end;target++){
for(int k=1;k<=cnt;k++){
int count=0;
for(int i=1;i<=6;i++){
if(target-i>=0) count+=dp[target-i][k-1];
}
dp[target][k]=count;
}
if(target>=start){
list.add(1.0/Math.pow(6,n)*dp[target][cnt]);
}
}
}
}
运行结果
共勉
最后,我想送给大家一句一直激励我的座右铭,希望可以与大家共勉!
文章来源:https://www.toymoban.com/news/detail-418574.html
文章来源地址https://www.toymoban.com/news/detail-418574.html
到了这里,关于【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!