二维动态规划。

题目链接-来源：力扣（LeetCode）

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例 1:

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

思路：

暴力解法会导致 O(6^n) 的复杂度。因此必须另寻他解。考虑利用动态规划降低复杂度。
对于某一个骰子，其结果很简单，单次点数 1 ~ 6 都是 1/6 概率。我们需要掷 n 次骰子，对于第 n 次投掷，总点数为 k 的概率记为 f(n, k)，则有 f(n, k) = f(1, 6) * f(n - 1, k - 6) + f(1, 5) * f(n - 1, k - 5) + … + f(1, 1) * f(n - 1, k - 1)，其中 p(1, x) 即为单词投掷出 x 点的概率，恒等于 1/6。于是有
f(n, k) = 1/6 * (i = 1 ~ 6)Σf(n - 1, k - i)
这就是动态规划的递推公式，边界条件是当 k - i <= 0 时，不存在对应的骰子点数，访问这些区域会造成越界。我们可以稍作优化，将以上公式 n 替换为 n + 1，变形为 1/6 * (i = 1 ~ 6)Σf(n, k - i) = f(n + 1, k)
于是对于每一个 f(n, x)，我们可以直接将 f(n, x) * 1/6 分别累加到 f(n + 1, k + i) (i = 1 ~ 6) 当中。
细节：
每次递推 dp[n + 1][] 只需要用到上层数组 dp[n][]，因此只需用两个数组交替存储即可。
如果用 dp[i][j] 表示 「i 个骰子掷出 j 点数」。对于边界，dp[n][] 的起始索引应该是 dp[n][n]，而终点索引为 dp[n][n * 6] ，为了节约存储空间，也方便返回结果，我们规定 dp[n][] 的下标范围要减去 n，统一为 0 ~ n * 5。
dp[] 均初始化为 1/6，下层数组开辟为 dpn[5 * n + 1]，每次搬运结果时，遍历 dp[]，将元素 dp[i] * 1/6 累加 6 次到 dpn[i + 0] ~ dpn[i + 5]即可。

时间复杂度：O(n²)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public double[] dicesProbability(int n) {
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0/6.0);
        
        for (int i = 2; i <= n; i++) {
            double[] dpn = new double[5 * i + 1];
            int len = dp.length;
            for (int j = 0; j < len; j++){
                for (int k = 0; k < 6; k++) {
                    dpn[j + k] += dp[j] / 6.0;
                }
            }
            dp = dpn;
        }
        return dp;
    }
}