Problem172 桁の繰り返しが少ない数

問題

どの数字も3回を超えて現れないような18桁の数(先頭の0は許されない)はいくつあるか?

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        //場合の数[0123456789の登場数]なDP表
        var PrevDP = new Dictionary<string, long>();

        for (int I = 1; I <= 9; I++) {
            char[] wkCharArr = new string('0', 10).ToCharArray();
            wkCharArr[I]++;
            PrevDP.Add(new string(wkCharArr), 1);
        }

        for (int I = 2; I <= 18; I++) {
            var CurrDP = new Dictionary<string, long>();
            foreach (var EachPair in PrevDP) {
                for (int J = 0; J <= 9; J++) {
                    if (EachPair.Key[J] == '3') continue;
                    
                    char[] NewKeyArr = EachPair.Key.ToCharArray();
                    NewKeyArr[J]++;

                    string NewKeyStr = new string(NewKeyArr);
                    if (CurrDP.ContainsKey(NewKeyStr))
                        CurrDP[NewKeyStr] += EachPair.Value;
                    else CurrDP[NewKeyStr] = EachPair.Value;
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine("{0}通り", PrevDP.Values.Sum());
    }
}

実行結果

227485267000992000通り

解説

桁DPで解いてます。