Problem164 どの連続した3桁の和も与えられた数を超えない数

問題

どの連続した3桁の和も9以下のような(9以下は9を含む)
20桁の数(先頭の0は認めない)はいくつあるか?

ソース

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        //場合の数[現在の数字,1つ前の数字]なDP表
        long[,] PrevDP = new long[10, 10];
        for (int I = 1; I <= 9; I++)
            PrevDP[I, 0] = 1;

        for (int I = 2; I <= 20; I++) {
            long[,] CurrDP = new long[10, 10];

            for (int J = 0; J <= 9; J++) {
                for (int K = 0; K <= 9; K++) {
                    if (PrevDP[J, K] == 0) continue;

                    for (int NewVal = 0; NewVal <= 9; NewVal++) {
                        int SumVal = J + K + NewVal;
                        if (SumVal > 9) break;

                        int NewJ = NewVal;
                        int NewK = J;
                        CurrDP[NewJ, NewK] += PrevDP[J, K];
                    }
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine("Answer={0}", PrevDP.Cast<long>().Sum());
    }
}

実行結果

Answer=378158756814587

解説

桁DPで解いてます。