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

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

动态规划：已知n-1个骰子的所有情况，再增加一个骰子，可推出n个骰子的所有情况。增加的一个骰子的点数只有1-6种可能，与n-1个骰子对应点数相乘，可得到n个骰子点数的一种情况，遍历所有情况即可。

class Solution {
    public double[] dicesProbability(int n) {
        double[][] dp = new double[n + 1][6 * n + 1];
        for(int i = 1; i <= 6; i++){
            dp[1][i] = 1.0 / 6;
        }

        for(int i = 2; i <= n; i++){  // 遍历骰子个数
            for(int j = i; j <= 6 * i; j++){  // 骰子个数确定时，遍历所有点数可能的情况
                for(int k = 1; k <= 6; k++){  // 新增的一个骰子点数有1-6种可能的情况
                    if(j - k > 0) dp[i][j] += dp[i - 1][j - k] / 6.0;
                }
            }
        }

        double[] res = new double[5 * n + 1];
        for(int i = 0; i < res.length; i++) res[i] = dp[n][i + n];
        return res;
    }
}