case1:暴力枚举,直接超时,时间复杂度O(6^n), 空间复杂度O(n),dfs不减枝的话会穷举所有可能，这里每一次有6种可能，共做n次，所有时间复杂度为O(6^n)
class Solution { double totalCount = 0.0; public void dfs(int n,int sum,Map<Integer,Integer>map){ if(n==0) { map.put(sum,map.getOrDefault(sum,0)+1); totalCount++; return; } for(int digtial=1;digtial<=6;digtial++){ dfs(n-1,sum+digtial,map); } } public double[] twoSum(int n) { if(n<=0) return new double[0]; //Map用于记录<sum,count> Map<Integer,Integer> map = new HashMap<>(); dfs(n,0,map); double[] pro = new double[map.size()]; int idx = 0; for(int i:map.values()){ pro[idx++] = i/totalCount; } return pro; } }case2: 思想：将n个骰子各掷1次，等价于将1个骰子掷n次，所以，总共有6^n个组合方式。所以和的所有取值为从最小:k,k+1,k+2…6*k。(k=1…n) 然后我们就可以利用dp思想了 dp[k][counts] 表示掷k次后和为counts的组合方式数 状态转移方程： dp[k][counts] += dp[k-1][counts-j] if(counts>j) else:+0 其中j=1,2,3…6也就是每个骰子的数值,条件是counts>j而不是counts>=j,是为了跳过计算k=1时的情况 时间复杂度O(n*(n+1)/2),空间复杂度O(n^2)
class Solution { public double[] twoSum(int n) { double total = Math.pow(6,n); int[][]dp = new int[n+1][6*n+1];//k可以取到n,counts可以取到6*n，所以在定义时不能直接写乘[n][6*n] double[]res = new double[5*n+1];//和可以从n取到6*n,所以总共有6n-n+1=5n+1个取值 //临界条件,掷1次骰子时各和只有1种组合方式 for(int counts =1;counts<=6;counts++){ dp[1][counts] = 1; } //遍历求取每个状态 for(int k=1;k<=n;k++){ for(int counts =k;counts<=6*k;counts++){ //每种状态可以有6种选择 for(int j=1;j<=6;j++){ dp[k][counts] +=(counts>j)?dp[k-1][counts-j]:0;//条件是counts>j而不是counts>=j,是为了跳过计算k=1时的情况 //最后一次掷骰子时，直接计算其出现的概率 if(k==n){ res[counts-k] = dp[k][counts]/total;//注意这里可以直接用counts-k来确定counts在最终结果数组中的下标，0，1... } } } } return res; } }