??作者簡介：碩風和煒，CSDN-Java領域新星創(chuàng)作者??，保研|國家獎學金|高中學習JAVA|大學完善JAVA開發(fā)技術棧|面試刷題|面經(jīng)八股文|經(jīng)驗分享|好用的網(wǎng)站工具分享??????
??座右銘：人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？??????

題目鏈接

劍指 Offer 60. n個骰子的點數(shù)

題目描述

把n個骰子扔在地上，所有骰子朝上一面的點數(shù)之和為s。輸入n，打印出s的所有可能的值出現(xiàn)的概率。

你需要用一個浮點數(shù)數(shù)組返回答案，其中第 i 個元素代表這 n 個骰子所能擲出的點數(shù)集合中第 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

求解思路&實現(xiàn)代碼&運行結果

暴力遞歸

求解思路

1. 為了能夠讓同學們更好的理解這個過程，我特意將整個思考的過程以及作圖的過程都繪制在下面這張圖中，希望可以通過下面這張圖更好的幫助你理解整個過程，大家可以結合這張圖來理解整個題目的求解思路。

實現(xiàn)代碼

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;
    }
}

運行結果

記憶化搜索

求解思路

1. 根據(jù)我們遞歸的分析，在遞歸的過程中會產(chǎn)生重復的子過程，所以我們想到了加一個緩存表，也就是我們的記憶化搜索。

實現(xiàn)代碼

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;
    }
}

運行結果

動態(tài)規(guī)劃

求解思路

1. 接下來我們根據(jù)之前的遞歸思路以及記憶化緩存改寫動態(tài)規(guī)劃。

實現(xiàn)代碼

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]);
            }   
        }
    }
}

運行結果

共勉

最后，我想送給大家一句一直激勵我的座右銘，希望可以與大家共勉！

文章來源地址http://www.zghlxwxcb.cn/news/detail-418574.html

到了這里，關于【LeetCode: 劍指 Offer 60. n個骰子的點數(shù) | 數(shù)學+ 暴力遞歸=＞記憶化搜索=＞動態(tài)規(guī)劃】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！