TopCoder SRM 523 Div1 Medium: BricksN

解法

メモ化再帰。「あっ!この問題SRMで見たことある!」感がすごい。

kenkoooo.hatenablog.com
kenkoooo.hatenablog.com
kenkoooo.hatenablog.com
kenkoooo.hatenablog.com

コード

import java.util.Arrays;

public class BricksN {
	private final int MOD = (int) 1e9 + 7;
	private int H;
	private long[][] dp;
	private long[] block;

	public int countStructures(int w, int h, int k) {
		this.H = h;

		// block[i]:= 幅iのブロックの作り方
		block = new long[w + 1];
		block[0] = 1;
		for (int i = 0; i < w; i++) {
			for (int b = 1; b <= k; b++) {
				if (i + b <= w) {
					block[i + b] = (block[i + b] + block[i]) % MOD;
				}
			}
		}

		// dp[h][n]:= 高さhにあるn個の連続した区間の積み方
		dp = new long[h + 1][w + 1];
		for (int i = 0; i < dp.length; i++) {
			Arrays.fill(dp[i], -1);
		}

		return (int) dfs(0, w);
	}

	// メモ化再帰
	private long dfs(int h, int n) {
		if (n == 0) {
			return 1;
		}
		if (h >= H) {
			return 1;
		}
		if (dp[h][n] >= 0) {
			return dp[h][n];
		}

		dp[h][n] = 0;

		// 左端に幅kのブロックを置いた時、右の幅n-1-kの部分の積み方も考える
		for (int k = 0; k <= n; k++) {
			long tmp = dfs(h + 1, k) * block[k];
			tmp %= MOD;
			if (n - 1 - k >= 0) {
				tmp *= dfs(h, n - 1 - k);
				tmp %= MOD;
			}
			dp[h][n] += tmp;
			dp[h][n] %= MOD;
		}
		return dp[h][n];
	}

}