/*一个类似24点的游戏，假设牌桌上有无数张1-10的牌，然后你手上的牌的总和是k，现在你可以随机到牌桌上抽牌加到总和里，如果你手上牌的总和在20-25之间就是win，如果总和超过25就是lose，现在让你求lose的概率。这一题我好像在地里见到过但是当时那个楼主说他没有做出来，所以我就也附上一下我的大概解法。首先因为每张牌都是无数张，所以抽任何一张牌的概率都是0.1。然后就是要考虑到有很多重复的情况，所以用dp或者recursion with memoization其实都可以。我是用dp做的，从后往前推，所有的结束可能就是20 - 29 其中P(20)到P(25)= 0， P(26)到P(29) = 1。那么P(19) = 0.1*P(20) + 0.1*P(21)+.... 以此类推，最后算到P(k)followup：假设每张牌是n张. 这就比较麻烦了，因为抽牌的概率跟当前牌桌上每张牌的数量有关，所以用dp比较难做，我就改用recursion with memoization。不仅要存手上牌的总和还要存牌桌上每张牌的数量。*/public class Main {    public static void main(String[] args) {                //System.out.println(new Solution().chanceToLose());        //System.out.println("Hello World!");        System.out.println(new Solution().chanceToLose2(10));    }}class Solution{    public double chanceToLose(){        HashMap
     
       map = new HashMap<>();        return dfs(0,map);    }                public double dfs(int sum, HashMap
      
        map){        if(map.containsKey(sum)){            return map.get(sum);        }                double p = 0;        if(sum >= 20 && sum <= 25){           p = 0;        }        else if(sum > 25){            p = 1;        }        else{            double pp=0;            for(int i = 1; i <= 10; i++){                pp=pp+0.1*dfs(sum + i, map);            }            p = pp;        }        map.put(sum, p);        return p;    }          public double chanceToLose2(int n){        HashMap
       
         cardsLeft = new HashMap<>();        for(int i=1; i<=10; i++){            cardsLeft.put(i, n);        }        return dfs2(0, n*10, cardsLeft);    }        public double dfs2(int sum, int n, HashMap
        
          cardsLeft){        double p = 0;        if(sum >= 20 && sum <= 25){            p = 0;        }        else if (sum > 25){            p = 1;        }        else{            for(int key : cardsLeft.keySet()){                int num = cardsLeft.get(key);                if(num > 0){                    double cp = 1.0* num / n;                    HashMap
         
           cLeft = new HashMap<>(cardsLeft);                    cLeft.put(key, num-1);                    p = p + cp*dfs2(sum+key, n-1, cLeft);                }            }        }        return p;    }                }