きままにものづくり

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

SRM585Div1Easy

問題

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

解法

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

計算量

$O(N)$

コード