骰子求和
题目描述
扔n个骰子，向上面的数字之和为 S 。给定 Given n，请列出所有可能的 S 值及其相应的概率。
样例
给定n=1，返回
[ [1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]。
算法分析
该题目刚开始的标记为简单，所以我做完两道简单题目后直接就看了这道题目，结果被卡在这里了。后来实现了完整的算法，结果提交只是通过了一部分的数据测试。看看还剩2分钟就结束了，焦急了，回头再去看题目列表，发现该题的难度级别又被标记为困难了，而之前标记为困难的平面列表，又被标记为简单了。进去一看，果然很简单，5分钟内实现了算法，在Eclipse测试，然后提交，Accepted!。结果比赛也已经结束了，只算是做对了两道题。我了个去！主办方是否要检讨检讨？
不闲扯了，分析算法：
该问题的解题思路应该是采用递归的方法：给定n个骰子，那么可投掷出的数字为n6n。可能有人会疑惑n6n中会不会有某个数字骰子表达不出来，好疑惑，答案是不会，证明如下：假设有n个相同的单个容量为6的豌豆筒，我们有6n颗豌豆，那么这6n颗豌豆能且正好能放进这n个豌豆筒中，说明n个骰子可以表达出6n；现在从任意筒中取出一颗豌豆，筒中还剩6n-1颗豌豆，说明n颗骰子可以表达出6n-1；如果某个筒中只剩一颗豌豆了，那么我们再次取豌豆的时候就不从里面取了；重复一颗一颗地取豌豆，直到每个筒中只剩下一颗豌豆，这是筒中总共有n颗豌豆，说明n个骰子可以表达n。而从6n到n的过程中，因为我们是一颗一颗豌豆取出的，所以6n-1到n+1这些颗数都曾在筒中出现过。因此n颗骰子能表达6n到n的所有数字。
n个骰子总共可以表达的情况有Math.pow(6,n)种。考虑n个骰子可以表达num的情况数：
如果第一骰子投出1，那么我们只需关心剩下的n-1个骰子能表达的num-1的情况数；如果第一个骰子投出了2，那么我们只需关心剩下的n-1个骰子能表达的num-2的情况数，依此类推；当然要注意，第一个骰子最多投出6。这里就用到了递归的思想。求n个骰子投出num的情况数的时候，需要递归求n-1个骰子投出num-1,num-2,num-3...的情况，而求n-1个骰子投出num-1的情况数的时候，需要递归求n-2个骰子投出num-2,num-3,num-4...的情况；求n-1个骰子投出num-2的情况数的时候，需要递归求n-2个骰子投出num-3,num-4...的情况，这里看到会有重复求解的过程，因此为了优化算法，这里采用动态规划技术，以减少不必要的重复求解过程。使用HashMap<String,Double>来存储已经计算好的情况数。这里String作为键，用以标记“x个骰子投出y”，值Double为情况数。这里Double我本来用的是Integer，结果计算精度出现问题，后来用Long，还是显示有些测试精度存在问题，索性改成Double，就Accepted了。
PS:刚才又试了一下，Double和Long都好使，Integer会出现精度问题
Java算法实现
public class Solution {
/**
* @param n an integer
* @return a list of Map.Entry<sum, probability>
*/
public List<Map.Entry<Integer, Double>> dicesSum(int n) {
// Write your code here
// Ps. new AbstractMap.SimpleEntry<Integer, Double>(sum, pro)
// to create the pair
List<Map.Entry<Integer, Double>>list=new ArrayList<Map.Entry<Integer,Double>>(5*n+1);
Double pro=0.0;
double total=Math.pow(6, n);
double conditions=0; //刚开始我用的int，发现计算结果又精度问题，改成long还是有精度问题，最后改成double就没问题了
//但严格来说，情况数应该是整数，是没问题的，计算过程中没有出现溢出的情况，total已经是double了，
//难道 1/1.0 根1.0/1.0不一样？
HashMap<String,Double> hashMap=new HashMap<>();
for(int i=n;i<=6*n;i++){
pro=0.0;
conditions=findCombs(i, n,hashMap);
pro=conditions/total;
list.add(new AbstractMap.SimpleEntry<Integer, Double>(i,pro));
}
return list;
}
public static double findCombs(int num,int n,HashMap<String, Double>hashMap){
//为了简化计算，假设每个骰子最小值为0，最大值为5，共n个骰子
double total=0;
String key=String.valueOf(num)+","+String.valueOf(n);
if(hashMap.containsKey(key)){
return hashMap.get(key);
}
if(num<=0){
if(n>=1)
total=0;
else
total=1;//0 个骰子得到0 是可以的
}
else{
//num >0
if(n<1){
total=0;
}
else if(n==1){
if(num>6){
total=0;
}
else{
total=1;
}
}
else{
int ceil=num<=6?num:6;
for(int i=1;i<=ceil;i++){
total+=findCombs(num-i, n-1,hashMap);
}
}
}
hashMap.put(key, total);
return total;
}
}