题目链接

思路

动态规划问题中，只用考虑第 n 个阶段如何由第 n-1 个阶段转化过来

在本题中，就是投掷 n 个骰子的结果如何由投掷 n-1 个骰子的结果转化过来。

代码

class Solution {
    public double[] dicesProbability(int n) {
        // 在做 dp 题目的时候只需要考虑最终状态即可,比较容易写出状态表达式和状态转移方程
        // dp[i][j] 表示投掷完 i+1 个骰子之后,点数 j 出现的次数
        // dp[n][j] = sum(dp[n-1][j-i]) 其中 i = (1,2,3,4,5,6)
        double[] result = new double[n * 6 - n + 1];
        int[][] dp = new int[n + 1][n * 6 + 1];

        for(int i = 1; i <= 6; i++){
            dp[1][i] = 1;
        }
        for(int i = 2; i <= n; i++){
            for(int j = i; j <= 6 * i; j++){
                for(int k = 1; k <= 6 && k <= j; k++){
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }

        int index = 0;
        for(int i = n; i <= 6 * n; i++, index++){
            result[index] = 1.0 * dp[n][i] / Math.pow(6, n);
        }

        return result;
    }
}