隣り合わない最大値 (House Robber)

大きい順に取ると、負ける

数字が一列に並んでいて、そこから好きなだけ選んで合計を最大にします。ただし 隣り合う 2 つは同時に選べません。[2, 7, 9, 3, 1] なら、2 と 9 と 1 で 12 が最大です。一番大きい 9 を含む選び方が正解ですが、2 番目に大きい 7 は 9 の隣なので使えません。

まず思いつくのは、大きいものから順に取って隣だけ避ける方法です。[2, 1, 1, 2] で試してみます。

先頭の 2 を取ります。隣の 1 は取れません。次の 1 を取ります。すると最後の 2 が隣になって取れず、合計は 3 です。正解は両端の 2 と 2 で 4 なので、負けています。

目の前で一番得に見える選択が、後の選択肢を潰す。だからその場で決め切らず、両方の場合を最後まで持って比べる必要があります。

1 つずつ「取る」と「飛ばす」を比べる

左から 1 つずつ見ていき、「ここまでで作れる最大」を更新していきます。今見ている要素について、道は 2 本しかありません。

• 飛ばす — 答えは 1 つ前までの最大と同じ
• 取る — 1 つ前は使えないので、2 つ前までの最大に今の値を足す

大きいほうを選んで、今の答えにします。これを最後まで繰り返すだけです。ここで比べているのは要素の大きさではなく、そこまでの合計 である点に注意してください。

[2, 1, 1, 2] で追うと、答えは 2、2、3、4 と進みます。3 番目では、2 つ前までの 2 に今の 1 を足した 3 が、1 つ前までの 2 を上回りました。最後は、2 つ前までの 2 に 2 を足した 4 が、1 つ前までの 3 を上回ります。貪欲では逃した 4 が、ちゃんと出ています。

貪欲との違いは、3 番目で 1 を取ったことを確定させていない点です。取った場合と取らなかった場合の両方の合計を持ったまま先へ進むので、最後にひっくり返せます。

覚えるのは直前 2 つだけ

式に出てくるのは「1 つ前」と「2 つ前」だけで、それより古い値は二度と使いません。だから配列を全部持たなくても、変数 2 つで足ります。

このとき更新の順番に注意が要ります。

変数 2 つを両方 0 から始めると、要素が 0 個のときも 1 個のときも場合分けなしで正しく動きます。配列を作る書き方にすると、先頭と 2 番目の初期値を別に決める必要が出てきます。

やってみよう

• [1, 2, 3, 1] の答えは 4。2 と 1 を選んだ 3 ではない
• [2, 1] と [1, 2] はどちらも 2。隣り合っているので片方しか選べない
• 一列ではなく輪になっていたら (先頭と末尾も隣) どうなるか考える。先頭を除いた場合と末尾を除いた場合で 2 回計算するのが定石

1. 戻り値は選んだ要素の最大合計 (整数)
2. 隣り合う 2 要素を同時に選んではいけない
3. 空配列は 0、1 要素はその値を返す