（部分点解法）経路 [AtCoder Beginner Contest 034 C]

atcoder.jp

この問題は以前満点解法を記事にしましたが、部分点解法がDPなので、DPのいい練習になると思って部分点解法の記事も書いてみることにしました。

といっても、基本的には解説にある通りに実装するだけで、
イメージしやすいという点では一次元のDPより簡単かもしれません。

DP遷移式は

・dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007

です。

遷移をおこなう前に、i=0 or j=0 の領域を 1 で埋めておく必要があるので、注意が必要です。

また、数字が大きいので一見 int 型ではオーバーフローするように見えますが、

・dp[i-1][j] + dp[i][j-1]

の計算結果は最大でも 2000000012 で、int 型にギリギリ収まるので、二次元配列 dp は int 型で定義すればよいです。

void solve () {

	int h = nextInt(), w = nextInt();
	int[][] dp = new int[h][w];

	for (int i=0; i<h; i++) {
		for (int j=0; j<w; j++) {
			if (i==0 || j==0) dp[i][j] = 1;
			else break;
		}
	}

	for (int i=1; i<h; i++) {
		for (int j=1; j<w; j++) {
			dp[i][j] = (dp[i-1][j]+dp[i][j-1]) % MOD;
		}
	}

	out.println(dp[h-1][w-1]);

}