这篇文章主要介绍LeetCode如何计算n个骰子的点数,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
把n个骰子扔在地上,所有骰子朝上一面的点数之和为S。输入n,打印出S的所有可能的值出现的概率。
假设骰子有face面,有n个骰子,那么总排列数就有faceⁿ个。(例如,有3个6面骰子,那么其总排列数为6³=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(n²),空间复杂度为O(n²)。
以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 { @Test public void test() { SumOfNDices sd = new SumOfNDices(); double[] result = sd.getProbability(1); System.out.println(result.length); System.out.println(Arrays.toString(result)); } @Test public void test2() { SumOfNDices sd = new SumOfNDices(); double[] result = sd.getProbability(10); double[] result2 = sd.getProbability2(10); Assert.assertArrayEquals(result, result2, 1E-10); } @Test public void test3() { SumOfNDices sd = new SumOfNDices(); double[] result = sd.getProbability(10); double[] result3 = sd.getProbability3(10); Assert.assertArrayEquals(result, result3, 1E-10); } }
以上是“LeetCode如何计算n个骰子的点数”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。