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

class Solution {
    public double[] dicesProbability(int n) {
        double res[] = new double[n*5+1];
        double dp[][] = new double[n+1][n*6+1];
        
        // 首先将1个色子出6个值的概率输出
        for(int i=1;i<=6;i++){
            dp[1][i] = 1.0/6;
        }

        // 从两个色子的情况开始考虑
        for(int i=2;i<=n;i++){
            // 从最小可能出现的点数i开始遍历求解 2个色子开始最小的可能出现的值就是2，最大的值就是i*6
            for(int j=i;j<=i*6;j++){
                // 从当前色子从1到6的情况开始考虑 将单独的色子取遍6种情况打表
                for(int k=1;k<=6;k++){
                    // 判断当前的组合是否合法 去除无意义的解 遍历所有意义的解 将其概率求和
                    // 当前的j需要大于单个色子投出的值 合法性判断
                    if(j - k > 0)
                        dp[i][j] += dp[i-1][j-k]/6;
                    else
                        break;
                }
            }
        }
        
        // 构建返回解的形式
        // 构造解的返回形式 n个色子的结果共有5n+1种，由于n个色子的点数范围是[n,6n],数量是6n-n+1 = 5n+1
        for(int i=0;i<=5*n;i++){
            res[i] = dp[n][n+i];
        }

        return res;
    }
}