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になります。開始位置から一つおきに家を取ると、2 + 3 + 8 = 13にしかなりません。
発展問題
取得する家と合計の両方を返します。そのリストを再構築するには、テーブルから何を保持する必要がありますか。また、2つの累計だけでそれを実現できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最後の家を見てください。計画では、それを選ぶか、見送るかのどちらかです。それぞれの選択によって、何を解決する必要が残りますか？
家
k-1をスキップする場合、最善の選択は最初のk-1軒の家から得られる最善の選択です。家を選ぶ場合は、最初のk-2軒の家から得られる最善の選択にnums[k-1]を加えます。k軒の家に対する答えは、この2つのうち大きい方です。通りの始まりからの最良の合計を埋めていきます。家がない場合は 0 から始めます。それぞれに必要なのは直前の 2 つだけなので、変数は 2 つで十分です。
解説
近道は失敗します。1軒おきに選ぶと[5, 3, 4, 11, 2]の5と11を見逃し、最も裕福な家を最初に選ぶと[3, 4, 3]で損をします。代わりに、1軒ずつ判断しましょう。ある家までの最善の合計は、その2軒前までの最善の合計だけで決まります。
各家で両方の選択肢を試してみましょう
正しいが、最大のテストでは終わらない
考え方
どの計画も、最後の家を飛ばすか、奪うかのどちらかです。飛ばす場合、最初のn-1軒の家に対する最善の計画が残ります。奪う場合は、最初のn-2軒の家に対する最善の計画にnums[n-1]を加えます。したがって、most(k) = max(most(k-1), most(k-2) + nums[k-1])となり、most(0) = 0、most(1) = nums[0]です。この2つの分岐ですべての計画を網羅できるので、答えは正しいです。
分岐は重複しています。most(k-1)は再びmost(k-2)を求めるため、呼び出し回数はフィボナッチ数のように増加し、およそ1.6^nになります。家が40軒あると呼び出し回数は3億回を超え、nは10^4に達します。
アルゴリズム
- 最初の
k軒の家から取れる最大の額を返すヘルパーmost(k)を書きます。 kが0の場合は0を返し、kが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 個です。それぞれの答えを表bestに一度ずつ記録します。best[0] = 0とbest[1] = nums[0]から始め、k = 2から上へ順に埋めていけば、各計算で読み取る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つ前までの項目だけを参照するため、表の代わりに2つの数値を保持します。twoBackとoneBackは、それぞれ2軒前までと1軒前までの最良の合計です。xを持つ家について、新しい最良値はmax(oneBack, twoBack + x)です。次に、両方を1つずつずらします。どちらも最初の家の前にある空の通りを表す0から始めるため、家が1軒だけの通りでも特別な処理は必要ありません。時間計算量は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
落とし穴と境界ケース
oneBackकोtwoBackमें कॉपी करने से पहले ओवरराइट करना। इसके बाद वाला घर गलत कुल पढ़ता है। पहले नया सर्वोत्तम मान निकालें, फिर मानों को आगे खिसकाएँ, या दोनों को एक साथ असाइन करें।nums[1]पढ़ना, या शुरुआत में हीbest[1]औरbest[2]सेट करना। एक घर वाली सड़क पर, जैसे[0], दोनों तरीकों से समस्या होती है।- Lua और R में ऐरे की शुरुआत 1 से होती है, इसलिए घर
k-1की रकमnums[k]में होती है।
よくある質問3
House Robber の時間計算量と空間計算量は何ですか？
動的計画法では各家を一度ずつ調べるため、時間計算量は O(n) です。テーブル全体を使うと空間計算量は O(n) ですが、直近2つの合計だけを保持すれば O(1) に抑えられます。答えを保存しない単純な再帰では、約 1.6^n 回の呼び出しが発生します。
なぜ1軒おきに家を選ぶだけでは、House Robberは解けないのでしょうか？
最適な計画では、家を2軒続けて飛ばすこともあります。[10, 1, 1, 10]では、偶数番目の家と奇数番目の家の合計はどちらも11ですが、最初と最後の家を選ぶと20になります。
家が円形に並んでいる場合、「ハウス・ロバー」問題はどのように解きますか？
円形では、最初の家と最後の家は隣り合っているため、計画にはどちらか一方しか含められません。直線状の通りの場合の解法を2回実行します。1回目は最後の家を除き、2回目は最初の家を除いて、結果の大きい方を返します。家が1軒だけの場合は特別なケースで、答えはその家です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def rob(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [5, 3, 4, 11, 2]
期待される出力
16