TopCoder SRM 585: TrafficCongestionDivTwo
外周を沿うように、大きく「へ」の字に車を移動させると残った部分は、高さ 0 から treeHeight-2 まで完全二分木が2つずつになる。Editorial の図がわかりやすい。
このことから漸化式に帰着できるので、あとは動的計画法で求める。
最初 dp = new long[treeHeight+1]
としてたら、 treeHeight=0 のときに落ちてしまってた……
public class TrafficCongestionDivTwo { public long theMinCars(int treeHeight) { long[] dp = new long[100]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= treeHeight; i++) { for (int j = 0; j <= i - 2; j++) { dp[i] += dp[j] * 2; } dp[i]++; } return dp[treeHeight]; } }