题目要求：n个六面的骰子，扔一次之后和为k的概率是多少？给定骰子数量n和骰子的点数之和k，求概率res。
思路：动态规划dp。
问题分析：每个骰子的点数都是1~6，因此n个骰子的总点数和的范围是[n,6n]，需要计算点数之和恰好等于k的方案数。
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 - v] for v = 1 to 6。
3.dp数组如何初始化：dp[0][0] = 1，表示使用0个骰子，总点数和为0的方案数为1。在这里没有实际意义，只用作dp数组的初始化。
4.确定遍历顺序：本题相当于分组背包问题。有n个组（每组对应一个骰子），每组有6个物品（点数1~6），每组必须且只能选1个物品，求恰好凑成总重量k的方案数。因此在使用二维数组时，组内物品的遍历顺序无所谓。
附代码：
class Solution { public String probabilityOfSum(int n, int k) { // 如果 k 不在可能范围内，概率为 0 if (k < n || k > 6 * n) { return "0"; } // dp[i][s]：i 个骰子，点数和为 j 的方案数 long[][] dp = new long[n + 1][6 * n + 1]; dp[0][0] = 1; // i个骰子 for (int i = 1; i <= n; i++) { // j表示i的骰子可能的点数和，范围为[i,6 * i] for (int j = i; j <= 6 * i; j++) { // v表示第i个骰子可选点数，范围为[1,6] for (int v = 1; v <= 6; v++) { // j - v要大于等于0，因为第i个骰子的可选的点数一定不能超过点数和，否则需要排除 if (j - v >= 0) { // 因为v会从1-6中取值，所以要把这6种可能累加 dp[i][j] += dp[i - 1][j - v]; } } } } // 总方案数 = 6^n long total = (long) Math.pow(6, n); // 可选方案数 = dp[n][k] long ways = dp[n][k]; // 约分 long g = gcd(ways, total); ways /= g; total /= g; return ways + "/" + total; } // 递归求最大公约数（欧几里得算法，即辗转相除法） private long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } }ACM模式：
import java.util.Scanner; class Solution { public String probabilityOfSum(int n, int k) { // 如果 k 不在可能范围内，概率为 0 if (k < n || k > 6 * n) { return "0"; } // dp[i][s]：i 个骰子，点数和为 j 的方案数 long[][] dp = new long[n + 1][6 * n + 1]; dp[0][0] = 1; // i个骰子 for (int i = 1; i <= n; i++) { // j表示i的骰子可能的点数和，范围为[i,6 * i] for (int j = i; j <= 6 * i; j++) { // v表示第i个骰子可选点数，范围为[1,6] for (int v = 1; v <= 6; v++) { // j - v要大于等于0，因为第i个骰子的可选的点数一定不能超过点数和，否则需要排除 if (j - v >= 0) { // 因为v会从1-6中取值，所以要把这6种可能累加 dp[i][j] += dp[i - 1][j - v]; } } } } // 总方案数 = 6^n long total = (long) Math.pow(6, n); // 可选方案数 = dp[n][k] long ways = dp[n][k]; // 约分 long g = gcd(ways, total); ways /= g; total /= g; return ways + "/" + total; } // 递归求最大公约数（欧几里得算法，即辗转相除法） private long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取骰子个数 n 和目标和 k int n = scanner.nextInt(); int k = scanner.nextInt(); // 计算结果 Solution solution = new Solution(); String result = solution.probabilityOfSum(n, k); System.out.println(result); scanner.close(); } }
