動的計画法でnCrを求める

#導入
こんにちは。けちょんです。
皆さんは組み合わせの総数を出力するプログラムを書けますか？
自分は競技プロで出会ったときに書けませんでした。
恥ずかしくて復習です。

#方法
今回は以下の漸化式を利用して、動的計画法で導きます。

nCr = n-1Cr-1 + n-1Cr

ちなみに、この漸化式のイメージは以下です。

n個からr個を選ぶ組み合わせは、以下の和である。
（n個から一個除いて考える）
1.追加されている1個が選択されている場合
　総数はn-1個、選択する数は残りr-1個
2.追加されている1個が選択されていない場合
　総数はn-1個、選択する数は残りr個　

図で書きたかったんですが、怠けました。

ソースは以下です。

import java.util.Scanner;

public class Main {
	static Integer[][] dp;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int R = sc.nextInt();

		dp = new Integer[N + 1][R + 1];

		// 初期値を設定
		for (int i = 0; i <= N; i++) {
			dp[i][1] = i;
		}
		for (int i = 0; i <= R; i++) {
			dp[0][i] = 0;
		}

		// "nCr = nCn-r" を使い、計算量を節約
		if (R > N / 2) {
			R = N - R;
		}
		int res = comb(N, R);
		System.out.println(res);
	}

	private static int comb(int n, int r) {
		if (r == 0) {
			return 1;
		}
		// "nCr = n-1Cr-1 + n-1Cr"を使用
		return getInt(n - 1, r) + getInt(n - 1, r - 1);
	}

	private static int getInt(int n, int r) {
		if (dp[n][r] != null) {
			// 与えられた(n,r)に対して、dp表から値を返す。
			return dp[n][r].intValue();
		}
		// dp表に無い場合は、combに渡し、導出する
		return comb(n, r);
	}
}

ちゃんと動いていそうです。
ちなみに計算量はO(n^2)らしいです。
参考：https://www.slideshare.net/chokudai/abc021

動的計画法を使わないと計算量が莫大になるので注意です。

#次回
次回は逆元を用いる方法を紹介します。
計算量はなんと**O(n logp)**とのこと
※p = 10^9+7 であり、出力値をpで割る前提