Q23 ブラックジャックで大儲け！？

C#のソース

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        Solve(1, 4);
        Solve(10, 24);
    }

    static void Solve(int pFirstCoinCnt, int pGameCnt)
    {
        int UB = pFirstCoinCnt + pGameCnt;

        //場合の数[コインの枚数]なDP表
        int[] PrevDP = new int[UB + 1];
        PrevDP[pFirstCoinCnt] = 1;

        for (int I = 1; I <= pGameCnt; I++) {
            int[] CurrDP = new int[UB + 1];
            for (int J = 1; J <= UB; J++) {
                if (PrevDP[J] == 0) continue;

                Action<int> UpdateAct = (pNewJ) =>
                {
                    if (pNewJ == 0) return;
                    CurrDP[pNewJ] += PrevDP[J];
                };
                UpdateAct(J - 1);
                UpdateAct(J + 1);
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine("最初のコイン枚数={0}。ゲーム回数={1}の場合は、{2}通り",
            pFirstCoinCnt, pGameCnt, PrevDP.Sum());
    }
}

実行結果

最初のコイン枚数=1。ゲーム回数=4の場合は、6通り
最初のコイン枚数=10。ゲーム回数=24の場合は、16051010通り

解説

動的計画法でナイーブに解いてます。