きままにものづくり

日々の気付いたことなんかを書いてます。

SRM585Div1Easy

問題

高さNの二分木が与えられる。すべてのノードに車が通るようにするためには、最小でいくつの車が必要か求めよ。
ただし、車は他の車も含め一度通ったノードをもう一度通ることはできない。

解法

動的計画法で求まる。
 f(n) = f(n-1) + 2f(n-2)
一番外側のノードを一台の車に走らせると、n-2までの二分木が2個ずつできあがる。このまま、計算すると O(N^2)となってしまうので、一つ前の要素を用いて O(N)にする。

計算量

 O(N)

コード