例题：n个骰子的点数

• 链接：剑指offer60.n个骰子的点数

• 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。(1 <= n <= 11)

1.常规思路

s的范围应该为n到6n(最小为每一个骰子都是1，最大为每一个骰子都是6)
很直观的思路就是dfs搜索，枚举每一个可能出现的点数和s，然后每次搜索用掉一个骰子，点数和对应减少1到6点
如果骰子用完的时候点数和刚好减为0，则搜索到一种可以投掷出该点数的方案

2.DFS代码(超时)

class Solution {
    public double[] twoSum(int n) {
        int[] cnt = new int[5*n+1];
        for(int i = n; i <= 6*n; i++){
            cnt[i-n] = dfs(n, i);
        }
        int tot = 0;
        for(int x: cnt) tot += x;
        double[] res = new double[5*n+1];
        for(int i = 0; i < res.length; i++){
            res[i] = (double)cnt[i]/tot;
        }
        return res;
    }

    int dfs(int n, int sum){
        if(sum < 0) return 0;
        if(n == 0 && sum == 0) return 1;
        else if(n == 0 && sum != 0) return 0;

        int res = 0;
        for(int i = 1; i <= 6; i++){
            res += dfs(n-1, sum-i);
        }
        return res;
    }
}

3.优化

DFS的搜索时间复杂度是指数级别的，我们想办法优化
可以使用动态规划来存储已经搜索过的状态，f[i][j]表示用了i个骰子，当前点数为j的方案数
初始化：f[0][0] = 1表示用了0个骰子，点数为0，有一种方案
枚举用了几个骰子，当前点数为多少，最后一次投掷出的点数是多少(集合划分)，用三层循环求方案即可

4.DP代码

class Solution {
    public double[] twoSum(int n) {
        //前i个骰子，获得最大点数为j的方案数
        int[][] f = new int[n+1][n*6+1];
        f[0][0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i*6; j++){
                for(int k = 1; k <= 6; k++){
                    //j比k大，状态才有效
                    if(j >= k) f[i][j] += f[i-1][j-k];
                }
            }
        }
        int[] cnt = new int[5*n+1];
        int tot = 0;
        for(int i = 0; i < 5*n+1; i++) {
            cnt[i] = f[n][i+n];
            tot += cnt[i];
        }
        double[] res = new double[5*n+1];
        for(int i = 0; i < 5*n+1; i++){
            res[i] = (double)cnt[i]/tot;
        }
        return res;
    }
}

• 相似问题还有LeetCode1155.掷骰子的N种方法，骰子的面数不同，其他都一样