// 动态规划
class Solution {
public:
    vector<double> dicesProbability(int n) {
        // 保存概率结果
        vector<double> result;

        // 判断边界条件
        if(n == 0)  return result;

        // 计算所有可能出现的情况
        double sum = pow(6, n);

        // 定义状态(dp[n][s]: 当有 n 个骰子的时候，和为 s 的情况的个数)
        vector<vector<int>> dp(n + 1, vector<int>(6 * n + 1, 0));

        // 状态初始化(dp[1][1] = 1, dp[1][2] = 1, ...)
        for(int i = 1; i <= 6; ++i)
            dp[1][i] = 1;

        // 状态转移(当有 2 个以上骰子的时候)
        // 枚举骰子的个数
        for(int i = 2; i <= n; ++i)
        {
            // 枚举各个骰子的总和
            for(int j = i; j <= 6 * n; ++j)     
            {
                // 枚举当前骰子所出现的数字
                for(int k = 1; k <= 6; ++k)
                {
                    if(j - k < 0) break;
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }

        // 计算和为 i 时所出现的情况占总情况的概率
        for(int i = n; i <= 6 * n; ++i)
            result.push_back(dp[n][i] * 1.0 / sum);

        return result;
    }
};