House Robber
家が通りに沿って一列に並んでおり、nums[i]は家iにあるお金です。好きな家からお金を取れますが、隣り合う2軒の家から取ることはできません。取れる金額の合計の最大値を返してください。
関数
- numsinteger-array
- 通り順に並べた、各家にあるお金
- 戻り値integer
- 隣り合う2軒の家から取ることなく手にできる最大の合計
制約
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 1000- 答えは最大でも
5 × 106なので、符号付き32ビット整数に収まります。
例
- 入力
- nums = [5, 3, 4, 11, 2]
- 出力
- 16
- 説明
- 家0と家3から5と11を取り、合計16にします。2軒続けて飛ばしてもよく、この場合は他のどの計画よりも優れています。5 + 4 + 2 = 11、3 + 11 = 14です。
- 入力
- nums = [3, 10, 3]
- 出力
- 10
- 説明
- 両端の家を合わせると 3 + 3 = 6 です。真ん中の家だけで 10 になり、そこを選ぶと隣の家が両方とも選べなくなります。
- 入力
- nums = [2, 9, 3, 1, 8]
- 出力
- 17
- 説明
- 9 と 8 は、隣り合っていない 1 番と 4 番の家にあるので、合計は 17 です。最初から 1 つおきに家を選ぶと、2 + 3 + 8 = 13 にしかなりません。
提出時に隠しテスト+16件
発展問題
取り出す家と合計の両方を返します。そのリストを再構築するには、テーブルから何を保持する必要がありますか？また、2つの累計値でまだ実現できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最後の家を見てみましょう。計画では、その家を取るか、飛ばすかのどちらかです。それぞれの選択をした場合、残りは何を解けばよいでしょうか？
家
k-1をスキップする場合、最善の結果は最初のk-1軒の家から得られる最善の結果です。家を選ぶ場合は、最初のk-2軒の家から得られる最善の結果にnums[k-1]を加えます。k軒の家に対する答えは、この2つのうち大きい方です。通りの始まりからの最適な合計を埋めましょう。家がない場合は 0 から始めます。それぞれに必要なのは直前の 2 つだけなので、変数は 2 つで十分です。
解説
明らかな近道はうまくいきません。1軒おきに家を選ぶ方法では、[5, 3, 4, 11, 2]の5と11のように、2軒連続で飛ばすプランを見逃します。また、最も価値の高い家を最初に選ぶ方法も、[3, 4, 3]ではうまくいきません。この場合、4の家を選ぶと、合計6になる両隣の2軒を選べなくなるからです。うまくいくのは、家を1軒ずつ考えていく方法です。ある家までの最良の合計は、その2軒前までの最良の合計だけで決まります。
すべての家で両方の選択肢を試す
正しいが、最大のテストでは終わらない
考え方
最後の家、家 n-1 を見てみましょう。どの計画も、それを飛ばすか、取るかのどちらかです。飛ばす場合、できる最善の計画は最初の n-1 軒の家に対する最善の計画です。取る場合、家 n-2 は選べないため、最初の n-2 軒の家に対する最善の計画に nums[n-1] を加えます。答えはこの2つのうち大きい方です。
これを関数 most(k) として表します。最初の k 軒の家から取れる最大額です。most(k) = max(most(k-1), most(k-2) + nums[k-1]) で、家がない場合は most(0) = 0、1軒の場合は most(1) = nums[0] です。どの計画も最後の家を飛ばすか取るかのどちらかなので、この2つの分岐ですべての計画を網羅でき、結果は正しくなります。
分岐が重複するため、処理に時間がかかります。most(k-1) は再び most(k-2) を呼び出すため、同じ問いに何度も答えることになり、呼び出し回数はフィボナッチ数列のように増加し、およそ 1.6^n になります。家が40軒あるだけですでに3億回を超える呼び出しが必要で、テストには最大 10^4 軒の家が含まれます。また、呼び出しは n 階層までネストし、Python のデフォルト上限である1000を超えます。
アルゴリズム
- 最初の
k軒の家から取れる最大量を返すヘルパーmost(k)を記述します。 kが0の場合は0を、1の場合はnums[0]を返します。- それ以外の場合は、
skip = most(k-1)とtake = most(k-2) + nums[k-1]を計算します。 - 2つのうち大きい方を返します。答えは
most(n)です。
def rob(nums):
def most(k):
# The most you can take from the first k houses
if k == 0:
return 0
if k == 1:
return nums[0]
# Skip house k-1, or take it and skip house k-2
return max(most(k - 1), most(k - 2) + nums[k - 1])
return most(len(nums))ボトムアップテーブル
考え方
再帰処理で調べるのはmost(0)からmost(n)までだけなので、異なる問題はn + 1個です。それぞれの答えを一度だけ求めて表に格納し、読み取る答えがすでに表にある順序で表を埋めます。表は4つの要素で定義します。
状態：best[k]は、最初のk軒の家から得られる最大額です。漸化式：best[k] = max(best[k-1], best[k-2] + nums[k-1])：家k-1をスキップするか、隣の家より前までの最善の結果にその家の分を加えて取ります。基底ケース：best[0] = 0とbest[1] = nums[0]です。順序：kを2からnまで進めます。各項目はその前の2つの項目を参照するためです。
[5, 3, 4, 11, 2]の場合、表は0, 5, 5, 9, 16, 16です。k = 4では、家3をスキップした場合のbest[3] = 9と、best[2] = 5に11を加えて取る場合を比較し、16のほうが大きくなります。答えは最後の項目です。各項目の計算には比較が1回必要なので、時間計算量はO(n)、表に必要な空間はO(n)です。
アルゴリズム
- n + 1 個の要素を持つテーブル
bestを作成します。 best[0] = 0、best[1] = nums[0]に設定します。- 2 から n までの
kについて、best[k]をbest[k-1]とbest[k-2] + nums[k-1]の大きい方に設定します。 best[n]を返します。
def rob(nums):
n = len(nums)
# best[k] is the most you can take from the first k houses
best = [0] * (n + 1)
best[1] = nums[0]
for k in range(2, n + 1):
# Skip house k-1, or take it on top of the best from the first k-2 houses
best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
return best[n]2つの累計
考え方
表の各エントリが参照するのは、その直前にある2つのエントリだけです。best[k]がわかれば、best[k-2]が再び参照されることはありません。そこで、表の代わりに2つの数値を保持します。twoBackは2軒前までの家から得られる最大合計、oneBackは前の家までの最大合計です。
xを持つ家について、新しい最大値はmax(oneBack, twoBack + x)です。次に値をずらします。twoBackには以前のoneBackを、oneBackには新しい最大値を代入します。どちらも0から始めます。これは最初の家より前にある空の通りを表すため、最初の家に特別な処理は必要ありません。その最大値はmax(0, 0 + nums[0])です。
[5, 3, 4, 11, 2]の場合、ペアは(0, 0)、(0, 5)、(5, 5)、(5, 9)、(9, 16)、(16, 16)と変化し、oneBackは16になります。処理量は表を使う場合と同じO(n)で、メモリ使用量はO(1)に減ります。
アルゴリズム
twoBackとoneBackを 0 に設定します。nums内の各金額xについて、current = max(oneBack, twoBack + x)を計算します。oneBackをtwoBackに移し、その後currentをoneBackに移します。- 最後の家の後に、
oneBackを返します。
def rob(nums):
# The best totals from the houses up to two back and up to one back
two_back, one_back = 0, 0
for amount in nums:
# Skip this house, or take it on top of the best from two back
two_back, one_back = one_back, max(one_back, two_back + amount)
return one_back
落とし穴と境界ケース
ほとんどの誤答は、小さな入力ではうまくいく近道や、2つの合計を更新する順序の間違いが原因です。
- 偶数番目の家と奇数番目の家の金額を合計して、大きい方を選ぶ方法では、連続する2軒を飛ばす計画を見落とします。
[10, 1, 1, 10]では、どちらの合計も11ですが、家0と家3を選べば20になります。 - 最も金額の多い家を最初に選ぶ方法は、
[3, 4, 3]では失敗します。4を選ぶと、合わせて6になる両方の3を選べなくなります。 oneBackをtwoBackにコピーする前に上書きすると、次の家で必要になる値が失われます。まず新しい最大値を計算してから値をずらすか、言語で許されている場合は両方を同時に代入してください。nums[1]を読み込んだり、最初にbest[1]とbest[2]を設定したりすると、家が1軒しかない通りで問題が起きます。両方の合計を0から始めれば、特別なケースは不要です。- LuaとRでは配列のインデックスが1から始まるため、家
k-1にある金額はnums[k]です。
よくある質問4
House Robber の漸化式は何ですか？
最初の k 軒の家から得られる最良の合計は max(best[k-1], best[k-2] + nums[k-1]) です。家 k-1 を飛ばしてその前の家までの最良の合計を維持するか、家 k-1 を選んで隣の家より前で終わる最良の合計に加えます。基本ケースは、家がない場合は 0、家が 1 軒の場合は nums[0] です。
House Robber の時間計算量と空間計算量は何ですか？
動的計画法による解法では各家を1回ずつ確認するため、時間計算量は O(n) です。テーブル全体を使うと空間計算量は O(n) ですが、直近の2つの合計だけを保持すれば O(1) まで削減できます。答えを保存しない単純な再帰では、約 1.6^n 回の呼び出しが発生し、指数時間になります。
なぜ一軒おきに家を選んでも「House Robber」は解けないのでしょうか？
最適な計画では、2軒続けて家を飛ばすこともあります。[10, 1, 1, 10]では、偶数番目の家と奇数番目の家の合計はどちらも11ですが、最初と最後の家を取ると20になります。動的計画法では各家で飛ばす場合と取る場合を比較するため、こうした計画を見つけられます。
家が円形に並んでいる場合、House Robberをどのように解きますか？
円形では最初の家と最後の家は隣り合っているため、計画に含められるのはどちらか一方だけです。直線状の通りの解法を2回実行し、1回目は最後の家を除外し、2回目は最初の家を除外して、大きい方の結果を返します。家が1軒だけの通りは特別なケースで、答えはその家です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def rob(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [5, 3, 4, 11, 2]
期待値
16