問題

http://community.topcoder.com/stat?c=problem_statement&pm=11361&rd=15697

２分木の高さが与えられる。
車は一筆書きでそのセルを移動することができる。
ただし、一度車が通った道は行くことができない。

このとき、すべてのセルを移動するのに必要な車の台数を求める。

解き方

いくつか例を並べてみると、前の高さで必要な車の数＋２つ前で必要な車の数×２が答えになるという法則が出てくる。
あとはこれをｄｐで実装すればよい。


Challenge
高さが０のときはセルが1個存在するので答えは１になる。
値が０、１のときにコードがそのままでよいのか、例外条件を書かなければいけないのかを確かめる。
特にこの問題の場合は2つ前の配列を調べることからスタートは２からになるので
特に注意する。

dpの配列の宣言がなぜかうまく通らなかったのですが、vectorで宣言するとうまくいきました。１０＾６を超えるなど大きい場合のときはvectorを用いるのがよさそうです。

コード