Problem76 100の分割数の数を求める

問題

5は数の和として6通りに書くことができる:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
2つ以上の正整数の和としての100の表し方は何通りか.

ソース

using System;

class Program
{
    static void Main()
    {
        Console.WriteLine("DerivePatternCnt({0})={1}", 5, DerivePatternCnt(5));
        Console.WriteLine("DerivePatternCnt({0})={1}", 100, DerivePatternCnt(100));
    }

    static long DerivePatternCnt(int pN)
    {
        //場合の数[使用した枚数]なDP表
        int UB = pN;
        int[] DPArr = new int[UB + 1];
        DPArr[0] = 1;

        for (int I = 1; I <= pN - 1; I++) {
            for (int J = 0; J <= UB; J++) {
                if (DPArr[J] == 0) continue;

                int NewInd = J + I;
                if (UB < NewInd) break;
                DPArr[NewInd] += DPArr[J];
            }
        }
        return DPArr[UB];
    }
}

実行結果

DerivePatternCnt(5)=6
DerivePatternCnt(100)=190569291

解説

動的計画法で解いてます。