【剑指Offer】60. n个骰子的点数

浅浅的花香味﹌ 2022-12-02 15:03 108阅读 0赞

## 题目链接 ##

[Lintcode][]

## 题目描述 ##

把 n 个骰子扔在地上，求点数和为 s 的概率。  
![在这里插入图片描述][20200831164904971.png_pic_center]

## 解题思路 ##

### 动态规划 ###

使用一个二维数组 dp 存储点数出现的次数，其中 dp\[i\]\[j\] 表示前 i 个骰子产生点数 j 的次数。

空间复杂度：O(N2)

class Solution { 
        public double[] twoSum(int n) { 
            // 1 1-6(1+5*n) 6^1
            // 2 2-12 6^2
            double all = Math.pow(6, n);
            int[][] dp = new int[n+1][n*6+1];
            // 状态数组 
            dp[0][0] = 1;
            
            for(int i = 1; i <= n; i++) // i第几个色子
                for(int j = i; j <= 6*n; j++) // j当前值的和
                    for(int k = 1; k <= 6 && k<=j; k++) // k代表当前筛子的值
                        // 状态转移方程：i个色子和为j += i-1个色子和 第i个色子值为k
                        dp[i][j] += dp[i-1][j-k];
            double[] res = new double[1 + 5 * n];
            for(int i = n; i <= n*6; i++) 
                res[i - n] = dp[n][i] / all;
            return res;    
        }
    }

### 动态规划 + 旋转数组 ###

空间复杂度：O(N)

public List<Map.Entry<Integer, Double>> dicesSum(int n) { 
        final int face = 6;
        final int pointNum = face * n;
        long[][] dp = new long[2][pointNum + 1];
    
        for (int i = 1; i <= face; i++)
            dp[0][i] = 1;
    
        int flag = 1;                                     /* 旋转标记 */
        for (int i = 2; i <= n; i++, flag = 1 - flag) { 
            for (int j = 0; j <= pointNum; j++)
                dp[flag][j] = 0;                          /* 旋转数组清零 */
    
            for (int j = i; j <= pointNum; j++)
                for (int k = 1; k <= face && k <= j; k++)
                    dp[flag][j] += dp[1 - flag][j - k];
        }
    
        final double totalNum = Math.pow(6, n);
        List<Map.Entry<Integer, Double>> ret = new ArrayList<>();
        for (int i = n; i <= pointNum; i++)
            ret.add(new AbstractMap.SimpleEntry<>(i, dp[1 - flag][i] / totalNum));
    
        return ret;
    }

[Lintcode]: https://www.lintcode.com/en/problem/dices-sum/
[20200831164904971.png_pic_center]: /images/20221123/080dd33bb699476c9de38fab16604a75.png