程序员的算法趣题Q23: 二十一点通吃

1. 问题描述

赌场经典的二十一点游戏中，每回合下注 1枚硬币，赢了可以得到2枚硬币（+1枚），输了硬币会被收走（-1枚）。

假设最开始只拥有 1枚硬币，并且每回合下注1枚，那么4回合后还能剩余硬币（即没有输光）的硬币枚数变化情况如图所示，共有6种（圆形中间的数字代表硬币枚数）。

求最开始拥有10枚硬币时，持续24回合后硬币还能剩余的硬币枚数变化情况共有多少种？

2. 解法1--暴力搜索

每次投注有赢和输两种情况，则24次投注有总共种组合情况。注意，由于输光即游戏终止（即不准透支），因此输赢的顺序是有关系的。有些组合虽然从24把投注的总成绩来看是有硬币剩余的，但是在前面部分已经出现了输超过赢导致游戏提前终止了。

代码参见：point21game1()

由于没有把中间可以提前退出的情况考虑进去，本算法存在比较大的运算效率浪费。

3. 解法2--深度优先路径搜索

本问题可以按照深度优先路径搜索的思路来解决。这样可以有效地解决“解法1”的问题，即中间碰到已经输光的情况时，就不必沿着当前路径继续向下探索了。本系列有很多类似的题目，比如说，Q14: 国名接龙,Q18: 水果酥饼日，基本上可以用相同的框架来解决，这里不再做过多说明。

代码参见：point21game2()

意外的是，运行时间相比解法1并没有质的提升。不过从最终结果来看，在{10，24}的条件下，总的可能路径数接近，或者可以说本题的合法路径解是比较稠密的，因此DFS策略能带来的效率提升也就有限了。

4. 解法3--动态规划

进一步，本题还可以用动态规划的策略来解决。

考虑{ steps=k, coin=c}条件下的总可能路径数记为f(k,c)，当前下注的结果有两种可能，赢了则硬币数变为c+1（相应地步数k减一），输了则硬币数变为c-1（相应地步数k减一），因此可以得到以下递推关系式：

考虑本游戏的规则，当硬币变为0就表示失败了；另一方面，在硬币变为0之前步数用完了，就表示赢了。因此可以得到以上递推关系式的初始或边界条件：

代码参见：point21game3()

5. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Sat Sep 11 07:56:17 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
# from   collections import deque
import itertools as it

class Solution:
    def point21game1(self, coin:int, steps:int)->int:
        """
        Parameters
        ----------
        coin : The money for the start
        steps    : The number of steps of game

        Returns  : The number of paths for which there is money left        
        -------
        """
        k = 0
        count    = 0
        for item in it.product([1,-1],repeat=steps):
            # print(item)
            # k+=1
            # if k%(65536*4) == 0:
            #     print('k = {0}'.format(k//(65536*4)))
            
            balance = 0
            flag = True
            for i in item:                
                balance += i
                if balance == -coin:
                    flag = False
                    break
            if flag:
                count += 1
        return count

    def point21game2(self, coin:int, steps:int)->int:
        """
        Parameters
        ----------
        coin : The money for the start
        steps   : The number of steps of game

        Returns : The number of paths for which there is money left        
        -------
        """
        # path  = []
        # balance  = 0
        def explore(path, balance):
            if len(path)==steps and balance > (-coin):
                return 1
            
            count = 0
            for stake in [1,-1]:
                if (balance + stake) > (-coin):
                    count += explore(path+[stake],balance+stake)
                    
            return count
        
        return explore([],0)

    def point21game3(self, coin:int, steps:int)->int:
        """
        Parameters
        ----------
        coin : The money for the start
        steps    : The number of steps of game

        Returns  : The number of paths for which there is money left        
        -------
        """
        
        memo    = dict()
        def dp(k, c):
            # print('k={0},c={1}'.format(k,c))
            if (k,c) in memo:
                return memo[(k,c)]
            if c == 0:
                return 0
            if k == 0:
                return 1
                                
            return dp(k-1,c+1) + dp(k-1,c-1)
        
        return dp(steps,coin)

if __name__ == '__main__':        
            
    sln     = Solution()   
    coin = 1
    steps   = 4
    tStart  = time.perf_counter()
    count1  = sln.point21game1(coin, steps)
    count2  = sln.point21game2(coin, steps)
    count3  = sln.point21game3(coin, steps)
    tCost   = time.perf_counter() - tStart
    print('({0}, {1}), count1 = {2}, tCost = {3:6.3f}(sec)'.format(coin,steps,count1,tCost))        
    print('({0}, {1}), count2 = {2}, tCost = {3:6.3f}(sec)'.format(coin,steps,count2,tCost))        
    print('({0}, {1}), count3 = {2}, tCost = {3:6.3f}(sec)'.format(coin,steps,count3,tCost))        

    coin = 10
    steps    = 24
    tStart = time.perf_counter()
    count1 = sln.point21game1(coin, steps)
    tCost  = time.perf_counter() - tStart
    print('({0}, {1}), count1 = {2}, tCost = {3:6.3f}(sec)'.format(coin,steps,count1,tCost))            

    tStart = time.perf_counter()
    count2 = sln.point21game2(coin, steps)
    tCost  = time.perf_counter() - tStart
    print('({0}, {1}), count2 = {2}, tCost = {3:6.3f}(sec)'.format(coin,steps,count2,tCost))            
    
    tStart = time.perf_counter()
    count3 = sln.point21game3(coin, steps)
    tCost  = time.perf_counter() - tStart
    print('({0}, {1}), count3 = {2}, tCost = {3:6.3f}(sec)'.format(coin,steps,count3,tCost))   

运行结果：

意外的是，以递归调用方式实现的动态规划相比前两种解法也并没有看到运行性能的质的提升。。。是不是改用循环的方式开始实现会有更好的运行性能呢？

6. 后记

本题还可以转换为以下问题。考虑从(0,0)出发，只能往右（对应于输）或向上（对应于赢），考虑总步数24的前提下，限于在图中阴影区域中移动到达反斜对角线上各点{(0,24), (1,23),…, (16,8)}的总的可能路径数。