題目描述
把 n 個骰⼦扔在地上，所有骰⼦朝上⼀⾯的點數之和為 s 。輸⼊ n ，打印出 s 的所有可能的值出現的概率。
你需要⽤⼀個浮點數數組返回答案，其中第 i 個元素代表這 n 個骰⼦所能擲出的點數集合中第 i ⼩的那個的概率。
示例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]
思路及解答
暴力遞歸
枚舉所有骰子組合。遞歸計算每個骰子的點數，統計所有可能的和
public class Solution {
public double[] dicesProbability(int n) {
// 骰子點數範圍：n到6n，共5n+1種可能
int[] counts = new int[5 * n + 1];
// 遞歸統計所有可能的和
backtrack(n, 0, counts);
// 計算概率
double total = Math.pow(6, n);
double[] res = new double[counts.length];
for (int i = 0; i < counts.length; i++) {
res[i] = counts[i] / total;
}
return res;
}
private void backtrack(int remain, int sum, int[] counts) {
if (remain == 0) {
counts[sum - remain]++; // 統計和出現的次數
return;
}
// 當前骰子可以是1到6點
for (int i = 1; i <= 6; i++) {
backtrack(remain - 1, sum + i, counts);
}
}
}
如果使⽤暴⼒法，每⼀個骰⼦扔到 1 - 6 的概率都是 1/6，如果有 n 個 骰⼦，先不看重複的情況，⼀共有 $6^n$ 種情況，點數的範圍是 n ~ 6n ，也就是 5n+1 種。
- 時間複雜度：O(6ⁿ)，每個骰子有6種可能，n個骰子組合數為6ⁿ
- 空間複雜度：O(n)，遞歸調用棧的深度
以上的計算複雜度實在太⾼，我們不能接受。
動態規劃（推薦）
其實，這道題可以⽤動態規劃來處理， 1 個骰⼦的情況是已知的，⽽ 2 個骰⼦的情況呢？ 2 個骰⼦的情況，可以使⽤ 1 個骰⼦的情況推出， 3 個骰⼦的情況，可以使⽤ 2 個骰⼦的結果推出...
dp[i][j]表示i個骰子和為j的出現次數
執行過程示例（n=2）：
初始化dp[1][1]=1, dp[1][2]=1, ..., dp[1][6]=1
計算dp[2][2] = dp[1][1] = 1
dp[2][3] = dp[1][2] + dp[1][1] = 2
...
dp[2][12] = dp[1][11] (不存在) + ... + dp[1][6] = 1
public class Solution {
public double[] dicesProbability(int n) {
// dp[i][j]：i個骰子和為j的出現次數
int[][] dp = new int[n + 1][6 * n + 1];
// 初始化：1個骰子的情況
for (int j = 1; j <= 6; j++) {
dp[1][j] = 1;
}
// 填充狀態轉移表
for (int i = 2; i <= n; i++) { // 骰子數量從2到n
for (int j = i; j <= 6 * i; j++) { // 和的範圍：i到6i
for (int k = 1; k <= 6 && k < j; k++) { // 最後一個骰子的點數
dp[i][j] += dp[i - 1][j - k];
}
}
}
// 計算概率
double total = Math.pow(6, n);
double[] res = new double[5 * n + 1];
for (int j = n; j <= 6 * n; j++) {
res[j - n] = dp[n][j] / total;
}
return res;
}
}
- 時間複雜度：O(n²)，外層循環n次，內層循環最多6n次
- 空間複雜度：O(n²)，需要二維數組存儲中間結果
空間優化動態規劃
通過觀察發現當前狀態只依賴前一個狀態，可以優化空間。通過滾動數組減少空間使用
public class Solution {
public double[] dicesProbability(int n) {
// 使用兩個一維數組交替更新
int[] prev = new int[6 * n + 1];
int[] curr = new int[6 * n + 1];
// 初始化第一個骰子
for (int j = 1; j <= 6; j++) {
prev[j] = 1;
}
// 動態規劃填充
for (int i = 2; i <= n; i++) {
Arrays.fill(curr, 0); // 清空當前數組
for (int j = i; j <= 6 * i; j++) {
for (int k = 1; k <= 6 && k < j; k++) {
curr[j] += prev[j - k];
}
}
// 交換數組，準備下一輪
int[] temp = prev;
prev = curr;
curr = temp;
}
// 計算概率
double total = Math.pow(6, n);
double[] res = new double[5 * n + 1];
for (int j = n; j <= 6 * n; j++) {
res[j - n] = prev[j] / total;
}
return res;
}
}
- 時間複雜度：O(n²)，外層循環n次，內層循環最多6n次
- 空間複雜度：O(n)，只保留前一輪的結果，空間從O(n²)降到O(n)
數學公式法（多項式展開）
和為s的概率對應於(x+x²+...+x⁶)ⁿ展開式中xˢ的係數
public class Solution {
public double[] dicesProbability(int n) {
// 初始化多項式係數：1個骰子時各項係數為1
int[] coeff = new int[6 * n + 1];
for (int j = 1; j <= 6; j++) {
coeff[j] = 1;
}
// 多項式乘法：計算(1x+1x²+...+1x⁶)^n
for (int i = 2; i <= n; i++) {
int[] newCoeff = new int[6 * i + 1];
// 多項式乘法計算
for (int j = 1; j <= 6; j++) {
for (int k = i - 1; k <= 6 * (i - 1); k++) {
newCoeff[k + j] += coeff[k];
}
}
coeff = newCoeff;
}
// 計算概率
double total = Math.pow(6, n);
double[] res = new double[5 * n + 1];
for (int j = n; j <= 6 * n; j++) {
res[j - n] = coeff[j] / total;
}
return res;
}
}
- 時間複雜度：O(n²)，多項式乘法計算
- 空間複雜度：O(n)，存儲多項式係數
