題目

把n個骰子扔在地上，所有骰子朝上一面的點數之和為S。輸入n，打印出S的所有可能的值出現的概率。

分析

直接法

假設骰子有face面，有n個骰子，那么總排列數就有face?個。（例如，有3個6面骰子，那么其總排列數為63=216個）。所有骰子的和最小值為n（假設骰子最小值為1），而和最大值為n * face(例如，有3個6面骰子，那么和最大值為18)， 那么就有 （n * face - n + 1）個可能和值，那么新建長度為（n * face - n + 1）的一維數組進行統計不同S出現的次數。

然后骰子分別依次一個一個地投，并將其可能的值累加，最后將相應數組元素自增。

最后，遍歷數組，除以總排列數，得出結果。

該算法時間復雜度為O(face?)，當n越大，運算時間越長。（n從12開始增大，等待時間就開始難以接受）空間復雜度為O(n * face)。

動態規劃

確定問題解的表達式。可將f(n, s)表示n個骰子點數的和為s的排列情況總數

確定狀態轉移方程。n個骰子點數和為s的種類數只與n-1個骰子的和有關。因為一個普通骰子有六個點數，那么第n個骰子可能出現1到6的點數。所以第n個骰子點數為1的話，f(n,s)=f(n-1,s-1)，當第n個骰子點數為2的話，f(n,s)=f(n-1,s-2)，…，依次類推。在n-1個骰子的基礎上，再增加一個骰子出現點數和為s的結果只有這6種情況！那么有：

f(n,s) = f(n-1,s-1) + f(n-1,s-2) + f(n-1,s-3) + f(n-1,s-4) + f(n-1,s-5) + f(n-1,s-6)

上面就是狀態轉移方程，已知初始階段的解為：當n=1時, f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。

該算法時間復雜度為O(n2)，空間復雜度為O(n2)。

---

以3個6面骰子為例，所用到dp[i][j]數組如下圖所示。

i\j	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	1	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	1	2	3	4	5	6	5	4	3	2	1	0	0	0	0	0	0
3	0	0	0	1	3	6	10	15	21	25	27	27	25	21	15	10	6	3	1

放碼

一、直接法

import java.util.Arrays;public class SumOfNDices {public static int DICE_MAX_VALUE = 6;public double[] getProbability(int numOfDice) {if(numOfDice < 1) {throw new IllegalArgumentException();}int maxSum = DICE_MAX_VALUE * numOfDice;int[] sums = new int[maxSum - numOfDice + 1];Arrays.fill(sums, 0);setSums(numOfDice, sums);int total = (int)Math.pow(DICE_MAX_VALUE, numOfDice);return Arrays.stream(sums).mapToDouble((a)->(a * 1.0 / total)).toArray();}public void setSums(int numOfDice, int[] sums) {for(int i = 1; i <= DICE_MAX_VALUE; i++) {setSums(numOfDice, numOfDice - 1, i, sums);}}public void setSums(int numOfDice, int leftNumOfDice, int sum, int[] sums) {if(leftNumOfDice == 0) {sums[sum - numOfDice]++;}else {for(int i = 1; i <= DICE_MAX_VALUE; i++) {setSums(numOfDice, leftNumOfDice - 1, i + sum, sums);}}}}

二、動態規劃（二維數組）

public double[] getProbability2(int numOfDice) {if(numOfDice < 1) {throw new IllegalArgumentException();}int[][] dp = new int[numOfDice + 1][numOfDice * DICE_MAX_VALUE + 1];double[] result = new double[numOfDice * DICE_MAX_VALUE - numOfDice + 1];double total = Math.pow(DICE_MAX_VALUE, numOfDice);Arrays.fill(dp[1], 1, DICE_MAX_VALUE + 1, 1);for(int i = 1; i <= numOfDice; i++) {//如1, 2, 3, 4, 5, 6 for(int j = i; j <= DICE_MAX_VALUE * numOfDice; j++) {//n個6面骰子的和的可能值 ：6, 7, 8, 9, ...  for(int k = 1; k <= DICE_MAX_VALUE; k++) {//f(n, s) = f(n - 1, s - 1) + f(n - 1, s - 2) + f(n - 1, s - 3) + ...  dp[i][j] += (j >= k ? dp[i - 1][j - k] : 0); // j >= k 預防數組越界 if(i == numOfDice) {result[j - i] = dp[i][j] / total;}}}}return result;
}

由于每個dp[i][j]只于i-1時刻的狀態有關，所以可以刪去一個維度，簡化算法。

三、動態規劃（一維數組）

• 在上述解法的基礎上，刪去一個維度
• 第二個循環從后往前遍歷，避免覆蓋

public double[] getProbability3(int numOfDice) {if(numOfDice < 1) {throw new IllegalArgumentException();}int[] dp = new int[numOfDice * DICE_MAX_VALUE + 1];double[] result = new double[numOfDice * DICE_MAX_VALUE - numOfDice + 1];double total = Math.pow(DICE_MAX_VALUE, numOfDice);for(int i = 1; i <= DICE_MAX_VALUE; i++) {dp[i] = 1;result[i - 1] = 1.0 / DICE_MAX_VALUE;}for(int i = 2; i <= numOfDice; i++) {for(int j = DICE_MAX_VALUE * numOfDice; j >= 1; j--) {int temp = 0;for(int k = 1; k <= DICE_MAX_VALUE; k++) {temp += (j >= k) ? dp[j - k] : 0;}dp[j] = temp;if(i == numOfDice && j >= numOfDice) {result[j - i] = dp[j] / total;}}}return result;
}

測試

import java.util.Arrays;import org.junit.Assert;
import org.junit.Test;public class SumOfNDicesTest {@Testpublic void test() {SumOfNDices sd = new SumOfNDices();double[] result = sd.getProbability(1);System.out.println(result.length);System.out.println(Arrays.toString(result));}@Testpublic void test2() {SumOfNDices sd = new SumOfNDices();double[] result = sd.getProbability(10);double[] result2 = sd.getProbability2(10);Assert.assertArrayEquals(result, result2, 1E-10);}@Testpublic void test3() {SumOfNDices sd = new SumOfNDices();double[] result = sd.getProbability(10);double[] result3 = sd.getProbability3(10);Assert.assertArrayEquals(result, result3, 1E-10);}
}