36. House Robber II
読了目安 約1分
DP / LeetCode 213 (Medium) — 円環版 House Robber。場合分けで直線の DP に帰着する。
この章の目次
問題
LeetCode 213. House Robber II（Medium / カテゴリ: DP）
House Robber と同じ設定で、今回は家が円形に並んでいます。 つまり最初の家と最後の家が隣り合っています。 隣接する家を選ばずに盗める金額の最大値を返してください。
考え方
ヒント 1
円形で増えた制約は「最初の家と最後の家を同時に盗めない」ことだけです。 「最初の家を使わない」場合と「最後の家を使わない」場合に分ければ、どちらも直線の House Robber になります。
ヒント 2
状態・遷移・初期条件は前問とまったく同じです。
答えは、先頭を除いた列と末尾を除いた列それぞれに直線版 DP を適用した結果の最大値です。
家が 1 軒だけのときは両方の列が空になるので、先に nums[0] を返します。
Swift 実装のポイント
nums.dropFirst()とnums.dropLast()はArraySliceを返します。配列をコピーせずに部分列を扱えます。- 補助関数の引数型を
ArraySlice<Int>にすると、両方のスライスをそのまま渡せます。 nums.count == 1の場合分けを忘れると答えが 0 になります。
模範解答
class Solution {
func rob(_ nums: [Int]) -> Int {
if nums.count == 1 { return nums[0] }
return max(robLine(nums.dropFirst()), robLine(nums.dropLast()))
}
private func robLine(_ houses: ArraySlice<Int>) -> Int {
var prev = 0
var cur = 0
for x in houses {
(prev, cur) = (cur, max(cur, prev + x))
}
return cur
}
}計算量: O(N)。