題目敘述
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 400
題目翻譯
假設你是一個專業的搶匪，今天的目標是要搶劫一條街上的房子。每個房子都有防盜系統，其條件是當同一晚相鄰的兩間房子都被闖入時會報警。給定一個陣列 nums，每個索引代表每間房子最多可以搶到多少錢。計算出最多可以搶到多少錢。
解法解析
其解法可以分為三種：Recursion、Iteration 和空間優化後的 Iteration。因為搶了第一間房子的話就不能搶第二間，解答是依據每次的選擇堆疊而成的。所以是典型的 Dynamic programming 問題。
主要的關鍵邏輯就是，每次選擇房子的時候是拿後面兩個來比較。目前在 i = 0 的位置，因為搶了 i = 0 的房子的話，就不能搶 i = 1 的房子。這樣的話至少 i[0] + i[2] >= i[1]才比較有效益，不然的話就是選擇i[1]` 的房子了。每次的選擇都是基於此條件，最後堆疊出最後的答案。
解法範例
Go
Recursion with Memoization
func rob(nums []int) int {
if len(nums) == 0 {
return 0
}
var memo map[int]int = make(map[int]int, len(nums))
return robFrom(memo, 0, nums)
}
func robFrom(memo map[int]int, i int, nums []int) int {
if i >= len(nums) {
return 0
}
if _, ok := memo[i]; ok {
return memo[i]
}
if robFrom(memo, i+1, nums) > robFrom(memo, i+2, nums)+nums[i] {
memo[i] = robFrom(memo, i+1, nums)
} else {
memo[i] = robFrom(memo, i+2, nums) + nums[i]
}
return memo[i]
}
Dynamic Programming
func rob(nums []int) int {
if len(nums) == 0 {
return 0
}
var N int = len(nums)
var maxRobbedAmount []int = make([]int, N+1)
maxRobbedAmount[N], maxRobbedAmount[N-1] = 0, nums[N-1]
for i := N - 2; i >= 0; i-- {
if maxRobbedAmount[i+1] > maxRobbedAmount[i+2]+nums[i] {
maxRobbedAmount[i] = maxRobbedAmount[i+1]
} else {
maxRobbedAmount[i] = maxRobbedAmount[i+2] + nums[i]
}
}
return maxRobbedAmount[0]
}
Optimized Dynamic Programming
func rob(nums []int) int {
if len(nums) == 0 {
return 0
}
var N int = len(nums)
var robNext, robNextPlusOne int = nums[N-1], 0
for i := N - 2; i >= 0; i-- {
if robNext > robNextPlusOne+nums[i] {
robNext, robNextPlusOne = robNext, robNext
} else {
robNext, robNextPlusOne = robNextPlusOne+nums[i], robNext
}
}
return robNext
}
JavaScript
Recursion with Memoization
const rob = function (nums) {
const memo = {};
const robFrom = (i, rob_nums) => {
if (i >= rob_nums.length) {
return 0;
}
if (i in memo) {
return memo[i];
}
const ans = Math.max(rob_nums[i] + robFrom(i + 2, rob_nums), robFrom(i + 1, rob_nums));
memo[i] = ans;
return ans;
};
return robFrom(0, nums);
};
Dynamic Programming
const rob = function (nums) {
if (!nums) {
return 0;
}
const N = nums.length;
const maxRobbedAmount = new Array(N + 1).fill(0);
maxRobbedAmount[N] = 0;
maxRobbedAmount[N - 1] = nums[N - 1];
for (let i = N - 2; i >= 0; i--) {
maxRobbedAmount[i] = Math.max(nums[i] + maxRobbedAmount[i + 2], maxRobbedAmount[i + 1]);
}
return maxRobbedAmount[0];
};
Optimized Dynamic Programming
const rob = function (nums) {
if (!nums) {
return 0;
}
const N = nums.length;
let robNextPlusOne = 0,
robNext = nums[N - 1];
for (let i = N - 2; i >= 0; i--) {
const current = Math.max(robNext, robNextPlusOne + nums[i]);
robNextPlusOne = robNext;
robNext = current;
}
return robNext;
};
Kotlin
Recursion with Memoization
class Solution {
protected lateinit var memo: MutableMap<Int, Int>
fun rob(nums: IntArray): Int {
memo = mutableMapOf()
return robFrom(0, nums)
}
fun robFrom(i: Int, nums: IntArray): Int {
if (i >= nums.size) return 0
if (memo[i] != null) return memo[i]!!
val res = Math.max(robFrom(i + 1, nums), nums[i] + robFrom(i + 2, nums))
memo[i] = res
return res
}
}
Dynamic Programming
class Solution {
fun rob(nums: IntArray): Int {
if (nums.size == 0) {
return 0
}
val N: Int = nums.size
var maxRobbedAmount: IntArray = IntArray(N + 1)
maxRobbedAmount[N] = 0
maxRobbedAmount[N - 1] = nums[N - 1]
for (i in N - 2 downTo 0) {
maxRobbedAmount[i] = Math.max(maxRobbedAmount[i + 1], maxRobbedAmount[i + 2] + nums[i])
}
return maxRobbedAmount[0]
}
}
Optimized Dynamic Programming
class Solution {
fun rob(nums: IntArray): Int {
if (nums.size == 0) {
return 0
}
val N: Int = nums.size
var robNext: Int = nums[N - 1]
var robNextPlusOne: Int = 0
for (i in N - 2 downTo 0) {
val current: Int = Math.max(robNext, robNextPlusOne + nums[i])
robNextPlusOne = robNext
robNext = current
}
return robNext
}
}
PHP
Recursion with Memoization
class Solution
{
private $memo = [];
function rob($nums)
{
return $this->robFrom(0, $nums);
}
function robFrom($i, $nums)
{
if ($i >= count($nums)) {
return 0;
}
if (isset($this->memo[$i])) {
return $this->memo[$i];
}
$ans = max($this->robFrom($i + 1, $nums), $this->robFrom($i + 2, $nums) + $nums[$i]);
$this->memo[$i] = $ans;
return $ans;
}
}
Dynamic Programming
class Solution
{
function rob($nums)
{
if (empty($nums)) {
return 0;
}
$N = count($nums);
$maxRobbedAmount = array_fill(0, $N + 1, 0);
$maxRobbedAmount[$N] = 0;
$maxRobbedAmount[$N - 1] = $nums[$N - 1];
for ($i = $N - 2; $i >= 0; $i--) {
$maxRobbedAmount[$i] = max($maxRobbedAmount[$i + 1], $maxRobbedAmount[$i + 2] + $nums[$i]);
}
return $maxRobbedAmount[0];
}
}
Optimized Dynamic Programming
class Solution
{
function rob($nums)
{
if (empty($nums)) {
return 0;
}
$N = count($nums);
$robNext = $nums[$N - 1];
$robNextPlusOne = 0;
for ($i = $N - 2; $i >= 0; $i--) {
$current = max($robNext, $robNextPlusOne + $nums[$i]);
$robNextPlusOne = $robNext;
$robNext = $current;
}
return $robNext;
}
}
Python
Recursion with Memoization
class Solution:
def __init__(self) -> None:
self.memo: dict[int, int] = {}
def rob(self, nums: list[int]) -> int:
self.memo = {}
return self.robFrom(0, nums)
def robFrom(self, i: int, nums: list[int]) -> int:
if i >= len(nums):
return 0
if i in self.memo:
return self.memo[i]
ans: int = max(self.robFrom(i + 1, nums), self.robFrom(i + 2, nums) + nums[i])
self.memo[i] = ans
return ans
Dynamic Programming
class Solution:
def rob(self, nums: list[int]) -> int:
if not nums:
return 0
N: int = len(nums)
maxRobbedAmount: list[int | None] = [None for _ in range(N + 1)]
maxRobbedAmount[N], maxRobbedAmount[N - 1] = 0, nums[N - 1]
for i in range(N - 2, -1, -1):
maxRobbedAmount[i] = max(
maxRobbedAmount[i + 1], maxRobbedAmount[i + 2] + nums[i]
)
return maxRobbedAmount[0]
Optimized Dynamic Programming
class Solution:
def rob(self, nums: list[int]) -> int:
if not nums:
return 0
N: int = len(nums)
rob_next_plus_one: int = 0
rob_next: int = nums[N - 1]
for i in range(N - 2, -1, -1):
current: int = max(rob_next, rob_next_plus_one + nums[i])
rob_next_plus_one = rob_next
rob_next = current
return rob_next
Rust
Swift
Recursion with Memoization
class Solution {
var memo: [Int: Int] = [Int: Int]()
func rob(_ nums: [Int]) -> Int {
return robFrom(0, nums: nums)
}
func robFrom(_ i: Int, nums: [Int]) -> Int {
if i >= nums.count {
return 0
}
if let memoized: Int = memo[i] {
return memoized
}
let result: Int = max(robFrom(i + 1, nums: nums), nums[i] + robFrom(i + 2, nums: nums))
memo[i] = result
return result
}
}
Dynamic Programming
class Solution {
func rob(_ nums: [Int]) -> Int {
if nums.count == 0 {
return 0
}
let N: Int = nums.count
var maxRobbedAmount: [Int] = Array(repeating: 0, count: N + 1)
maxRobbedAmount[N] = 0
maxRobbedAmount[N - 1] = nums[N - 1]
for i: Int in (0..<N - 1).reversed() {
maxRobbedAmount[i] = max(maxRobbedAmount[i + 1], nums[i] + maxRobbedAmount[i + 2])
}
return maxRobbedAmount[0]
}
}
Optimized Dynamic Programming
class Solution {
func rob(_ nums: [Int]) -> Int {
if nums.count == 0 {
return 0
}
let N: Int = nums.count
var robNextPlusOne: Int = 0
var robNext: Int = nums[N - 1]
for i: Int in (0..<N - 1).reversed() {
let current: Int = max(robNext, nums[i] + robNextPlusOne)
robNextPlusOne = robNext
robNext = current
}
return robNext
}
}