TopCoder SRM 585: TrafficCongestionDivTwo

外周を沿うように、大きく「へ」の字に車を移動させると残った部分は、高さ 0 から treeHeight-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];
    }
}