TopCoder SRM585: TrafficCongestion

TrafficCongestionDivTwo の treeHeight の上限が 60 から 1000000 になったもの。

漸化式自体は、同じ

dp[i] = (sum 2*dp[j] where j <= i-2) + 1

だけど、これだと O(treeHeight^2) でTLEになる。

合計を求めるところがネックなので、dp[0], ... , dp[i-2]までの和を逐次的に更新して計算量を下げると O(TreeHeight) になる。

public class TrafficCongestion {
    public int theMinCars(int treeHeight) {
        int mod = 1000000007;
        long[] dp = new long[treeHeight + 10];
        dp[0] = 1;
        dp[1] = 1;
        long sum = 0;
        for (int i = 2; i <= treeHeight; i++) {
            sum += dp[i - 2];
            dp[i] = (sum * 2 + 1) % mod;
        }
        return (int)dp[treeHeight];
    }
}