前言
通过n个骰子不同点数和的不同概率来深刻理解动态规划问题，做到举一反三。
一、例题
1.1、题目
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
1.2、示例
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
限制：
1 <= n <= 11
二、题解
对于一个问题的分析，抓住核心逻辑是关键，而对于动态规划问题，找到其中的求解规律即可。
1）挖掘题目数据
A) n个骰子各种和的概率 = 一种和出现的次数 / 所有和出现的总次数
B) 每个骰子有6种可能，那么组合在一起就是n个6相乘，即所有和出现的总次数 = 6n；
C) 易知，和的范围为n – 6n，最小全为1，最大全为6。
D) 代码体现
//所有可能和
double[] res = new double[5 * n + 1];
//所有组合的总数
double total = Math.pow(6, n);
2）找题目规律
求n个骰子落下，各和概率，那么让n取最小，一步一步来，即n = 1，可以容易得出各和出现的次数如下表，
| sum = 1 | sum = 2 | sum = 3 | sum = 4 | sum = 5 | sum = 6 |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 |
n = 2时，它与n = 1之间有什么联系呐？n = 2比n = 1多了一个骰子，多出的这一个骰子就可能出现1 – 6。所以当和固定为s，则s出现的情况为，
| 后一个骰子点数 | 前面所有骰子点数和 |
|---|---|
| 1 | s-1 |
| 2 | s-2 |
| 3 | s-3 |
| 4 | s-4 |
| 5 | s-5 |
| 6 | s-6 |
综述，设骰子个数为n，和为s出现的次数为f(n,s)，
代码体现为，
for (int i = 1; i <= n; i++) {
for (int j = i * 6; j >= i; j--) {
//求骰子为i且和为j的组合数
for (int k = 1; k <= 6; k++) {
dp[i][j] += j - k >= i - 1 ? dp[i - 1][j - k] : 0;
A) for (int k = 1; k <= 6; k++) {dp[i][j] += j - k >= i - 1 ? dp[i - 1][j - k] : 0;}体现上式中的递推公式;
B) i 代表骰子个数，j 代表骰子点数和，j >= i 体现上式中的条件一：s >= n；
C) k 代表最后一个骰子所摇出的点数，j - k >= i - 1体现上式中的条件二：s - i >= n-1；
注：接下来看完整解答
2.1、二维数组
//动态规划，抓寻找规律，把问题场景和分析描述清楚
public double[] dicesProbability(int n) {
//所有可能和
double[] res = new double[5 * n + 1];
//所有组合的总数
double total = Math.pow(6, n);
//动态规划所需二维数组
int[][] dp = new int[n + 1][6 * n + 1];
//初始状态即一个骰子点数和的情况
dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = dp[1][5] = dp[1][6] = 1;
//n个骰子且和为s的次数 == n-1个骰子且和为s-6,s-5,...,s-1的情况之和。
for (int i = 1; i <= n; i++) {
for (int j = i * 6; j >= i; j--) {
//求骰子个数为i且点数和为j各自出现的次数
for (int k = 1; k <= 6; k++) {
dp[i][j] += j - k >= i - 1 ? dp[i - 1][j - k] : 0;
}
//最后一轮更新，把结果填入res中。
if (i == n)
res[j - n] = dp[i][j] / total;
}
}
//返回结果
return res;
}
2.2、一维数组
可以发现更新骰子数为n时，只用到了n-1的点数和的个数，所以可以用一个一维数组存n-1的点数和的个数。
一处创新和两处注意事项
A）改变初始状态，把初始状态设为n = 0，即摇出的点数和s = 0的次数为1，其它都为0。那么n = 1时，点数和为1 – 6的情况为1+0 = 1，2+0 = 2，…，6+0 = 6，即6种和情况出现次数都为1，回到上面二维dp的初始化情况。
B）for (int j = i * 6; j >= i; j--)必须从后往前更新，因为后面的值更新需要用到前面的值，防止值覆盖。
C）对于单个一维数组从后往前更新时，在刚开始更新之前需要初始化当前值为0，避免加上“脏值”。
//改进，采用一维dp
public double[] dicesProbability(int n) {
//所有可能和
double[] res = new double[5 * n + 1];
//所有组合的总数
double total = Math.pow(6, n);
//动态规划所需一维数组
int[] dp = new int[6 * n + 1];
//新的初始状态
dp[0] = 1;
//动态规划，抓住寻找规律，把问题描述清楚
//n个骰子且和为s的次数==n-1个骰子且和为s-6,s-5,...,s-1的情况之和。
for (int i = 1; i <= n; i++) {
//为了不覆盖常用的临时部分，即temp里前面的部分，所以采用从后往前更新。
for (int j = 6 * i; j >= i; j--) {
//将要更新的状态初始化为0
dp[j] = 0;
//求骰子为i且和为j的组合数
for (int k = 1; k <= 6; k++) {
dp[j] += j - k >= i - 1 ? dp[j - k] : 0;
}
if (i == n)
res[j - n] = dp[j] / total;
}
}
return res;
}
2.3、直接上概率
有了上面的知识沉淀，那么用概率来解题也就是换个马甲。
//上概率
public double[] dicesProbability3(int n) {
//所有组合的总数
double total = Math.pow(6, n);
//动态规划所需一维数组
double[] dp = new double[6 * n + 1];
//新的初始状态
dp[0] = 1.0;
//动态规划，抓住寻找规律，把问题描述清楚
//n个骰子且和为s的次数==n-1个骰子且和为s-6,s-5,...,s-1的情况之和。
for (int i = 1; i <= n; i++) {
//为了不覆盖常用的临时部分，即temp里前面的部分，所以采用从后往前更新。
for (int j = 6 * i; j >= i; j--) {
//将要更新的状态初始化为0
dp[j] = 0;
//求骰子为i且和为j的组合数概率
for (int k = 1; k <= 6; k++) {
dp[j] += j - k >= i - 1 ? dp[j - k] * 1 / 6d : 0;
}
}
}
return Arrays.copyOfRange(dp, n, 6 * n + 1);
}
总结
1）动态规划，分析出问题中的循序渐进的规律。
2）动态规划三关键：初始状态、状态更新方程（递推公式）、最终结果。