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))

運行結果：