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

https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/

动态规划：由于每个骰子是独立的，且扔第 N 个骰子得到的点数和与 N-1 个有关，可以考虑用动态规划完成。

假设已知 n - 1 个骰子的解 f(n - 1)，此时添加一枚骰子，求 n 个骰子的点数和为 x 的概率 f(n, x)。

当添加的第 n 个骰子点数为 1，为了凑成 x，前面 n - 1 个的点数和就要是 x - 1。同理，当此骰子为 2 时，前 n - 1 个骰子应为 x - 2 。

因此，第 n 个骰子点数和就是第投出它本身的点数的概率（都是 1/6）乘以第 n - 1 个骰子的概率。即：

$ f(n, x) = ∑_i^6 1/6 * f(n - 1, x - i) $

得到递推公式即可写出 DP，从底向上构建比较方便。遍历每个 f(n - 1, j)，统计它对 f(n, j + i)（i=1..6）的贡献。

func dicesProbability(n int) []float64 {
    dp := make([]float64, 6)
    for i := range dp {
        dp[i] = 1.0 / 6
    }

    for i := 2; i <= n; i++ {
        tmp := make([]float64, 5*i+1)
        for j := range dp {
            for k := 0; k < 6; k++ {
                tmp[j+k] += dp[j] / 6
            }
        }
        dp = tmp
    }
    return dp
}

由于数组是有偏移量的，所以 k 的索引是从 0 开始的。