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

一、思路：题目要求是计算掷n个骰子时，所有可能点数出现的概率。这道题可以用动态规划dp来做。

1.投掷n个骰子时，可能出现的总和最小值是n * 1，可能出现的总和最大值是n * 6。

2.从最小值到最大值中，所有连续的整数都是可以取到的，这是因为可以通过每次增加1点的点数的方式来调整骰子点数，从而得到中间的所有整数。因此所有的总和值构成了一个连续的整数区间。

3.因此所有可能出现的点数的总数量 = 6n - n + 1 = 5n + 1。

二、动态规划dp

1.确定dp数组及其下标的含义：dp[i][j]表示投掷i个骰子，点数总和恰好等于j的概率。

2.确定递推公式：

可知i个骰子的情况可以由i - 1个骰子的情况推出。

（1）因此dp[i][j] = dp[i - 1][j - 6] + dp[i - 1][[j - 5] + dp[i - 1][j - 4] + dp[i - 1][j - 3] + dp[i - 1][j - 2] + dp[i - 1][j - 1]。

（2）即：dp[i][j] = dp[i - 1][j - k] for k = 1 to 6。

3.dp数组如何初始化：dp[1][j]=1/6​ for j = 1 to 6。表示使用1个骰子的时候，点数总和恰好等于1，2，3，4，5，6的概率均为1/6。

4.确定遍历顺序：从前往后遍历即可。在二维dp中遍历顺序其实不太敏感。因为我们在用二维数组存储所有状态，每个状态只依赖上一行的数据。

附代码：

class Solution { public double[] dicesProbability(int n) { // dp[i][j] 表示投掷 i 个骰子，点数和为 s 的概率 // i 的范围：0 ~ n // j 的范围：0 ~ 6*n（但实际有效范围是 i ~ 6*i） double[][] dp = new double[n + 1][6 * n + 1]; // 初始化：1个骰子的情况 for (int j = 1; j <= 6; j++) { dp[1][j] = 1.0 / 6.0; } // 从第2个骰子开始递推 for (int i = 2; i <= n; i++) { // 当前i个骰子的点数和范围：i ~ 6*i for (int j = i; j <= 6 * i; j++) { // 第i个骰子掷出k（1~6），则前i-1个骰子的和为 j-k for (int k = 1; k <= 6; k++) { int prevSum = j - k; // 检查前i-1个骰子的和是否有效，即是否大于i - 1(对应点数和全为1的情况) if (prevSum >= i - 1){ // 前i - 1个骰子点数总和等于j - k的概率 * 第i个骰子点数为1/6的概率 // 因为k会从1-6中取值，所以要把这6种可能累加 dp[i][j] += dp[i - 1][prevSum] * (1.0 / 6.0); } } } } // 提取结果：n个骰子的有效范围是 n ~ 6n int total = 5 * n + 1; double[] result = new double[total]; for (int i = 0; i < total; i++) { // 索引转换，n的骰子时的点数总和范围为n到6n，对应j // 对应的dp数组的位置即为dp[n][n]到dp[n][6n] result[i] = dp[n][n + i]; } return result; } }

ACM模式：

import java.util.Scanner; class Solution { public double[] dicesProbability(int n) { // dp[i][j] 表示投掷 i 个骰子，点数和为 s 的概率 // i 的范围：0 ~ n // j 的范围：0 ~ 6*n（但实际有效范围是 i ~ 6*i） double[][] dp = new double[n + 1][6 * n + 1]; // 初始化：1个骰子的情况 for (int j = 1; j <= 6; j++) { dp[1][j] = 1.0 / 6.0; } // 从第2个骰子开始递推 for (int i = 2; i <= n; i++) { // 当前i个骰子的点数和范围：i ~ 6*i for (int j = i; j <= 6 * i; j++) { // 第i个骰子掷出k（1~6），则前i-1个骰子的和为 j-k for (int k = 1; k <= 6; k++) { int prevSum = j - k; // 检查前i-1个骰子的和是否有效，即是否大于i - 1(对应点数和全为1的情况) if (prevSum >= i - 1){ // 前i - 1个骰子点数总和等于j - k的概率 * 第i个骰子点数为1/6的概率 // 因为k会从1-6中取值，所以要把这6种可能累加 dp[i][j] += dp[i - 1][prevSum] * (1.0 / 6.0); } } } } // 提取结果：n个骰子的有效范围是 n ~ 6n int total = 5 * n + 1; double[] result = new double[total]; for (int i = 0; i < total; i++) { // 索引转换，n的骰子时的点数总和范围为n到6n，对应j // 对应的dp数组的位置即为dp[n][n]到dp[n][6n] result[i] = dp[n][n + i]; } return result; } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); scanner.close(); Solution solution = new Solution(); double[] result = solution.dicesProbability(n); for (int i = 0; i < result.length; i++) { System.out.printf("%.5f", result[i]); if (i < result.length - 1) { System.out.print(" "); } } System.out.println(); } }