dealer busted -

21点游戏
使用 dfs + memo 的概率题
给一个 input num，随机抽1~10的数字加到 num 去得到新的 sum，如果 sum < 20 继续抽数字加和，20 <= sum <= 25 算 win，25 < sum 算 lose，求 lose probability.
dfs permutation 的思路加上 memo，每一层尝试用 num += 1~10，然后 recursion。应该需要算 probability 的平均值，所以 dfs 需要返回 avg prob 和一个 count 用来重新计算 avg prob

题目：backjack / 21 点， 给你一堆牌，从1到10，每张牌被抽的概率为1/10，问你dealer busted的概率是多少？
1. 如果dealer点数和不到17，将继续从牌堆抽牌；
2. 如果dealer点数和是在17-21，dealer stands，不继续抽牌;
3. 如果dealer点数和大于21，dealer busted；
条件2和条件3视为结束抽牌。

牌只有1-10点，如果还没满17点就要再拿一张，问超过21点的机率是多少？
DP问题，但面试时太紧张，不知道怎么设定DP，尤其是被一直抽牌有好几轮迷惑了。最后面试官提示，只要用DP计算拿到我点的机率，然后1-（P（17 ）+ P（18）+ P（19）+ P（20）+ P（21））就好，还是太浅了我

https://www.1point3acres.com/bbs ... read&tid=496031
https://www.1point3acres.com/bbs/thread-424050-1-1.html
https://www.1point3acres.com/bbs/thread-311254-1-1.html

我昨天才在二刷这题。。。 假设一次抽牌最多能抽到的数字是1-W 之间的数，而每个数字抽掉的概率都是一样的。因为能以一张牌的距离到达数字i 的方式只有i-1, i-2,...i-W, 要求抵达数字i的概率的话只要把i-1, i-2, ..., i-W的概率加总再除以W即可，也就是说去维护一个size为W的移动窗口就好了。 - dp 表示能到达i的概率 - dp = dp[i-1]/W + dp[i-2]/W +...+dp[i-W]/W - 用一个WSUM 表示dp[i-1]+...+dp[i-W] - 去维护这个WSUM，当i超过W以后每次loop 减去dp[i-W]，加上dp。如果i 已经超过结束点就不必再加 - 最后的概率是结束点到胜利点之间的概率加总 补充内容 (2019-3-15 02:48): 好吧，没看清楚题目，好像和LC的有点不一样

根据LC Lee215 思路转来的，没跑过 unittest 求指正

先假设开始数字一定不是负数，一次可以抽1-10，
每个数字抽到的概率都是十分之一，可能抽到同样的数字，
20分含以上游戏结束，低于25分（包含）赢，高于25分输，
求游戏结束后输掉的概率．

psum 为所有能以一张牌达到 i 分分数的分数的概率总和
假如开头为 7
8 可以从 7 开始，psum = sum(dp[7])
9 可以从 7 或 8 开始 psum = sum(dp[7..8])
10 可以从 7,8,9 开始 psum = sum(dp[7..9])
18 可以从 8, 9, 10, ...17开始，但不能从7开始, psum = sum(dp[8..17])

def the_21_game(start):

    if start >= 25:

        return 1.0

    if start >= 20:

        return 1 - (25 - start) / 10

    dp = [0] * 26

    dp[start] = psum = 1.0

     

    for i in range(start+1, 26):

        dp[i] = psum / 10

        if i-10 >= start: psum -= dp[i-10] # 把dp[i-10] 去掉，因为下一个 i 不能从 i-10 开始

        if i < 20: psum += dp[i]           # 游戏在20分以后就结束了，不会有从20分开始到达下一个 i分的情况

    return 1 - sum(dp[20:]) # 20-25 区间总和为赢的概率，1减去这个数值就是输的概率了

def the_21_game2():

    dp = [0] * 22

    dp[0] = psum = 1.0

    for i in range(1, 22):

        dp[i] = psum / 10

        if i-10 >= 0: psum -= dp[i-10]

        if i < 17: psum += dp[i]

    return 1 - sum(dp[17:])