# 198. House Robber

## 題目敘述

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 <= 100`
• `0 <= nums[i] <= 400`

## 解法解析

### 解法範例

#### 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
``````/**
* @param {number[]} nums
* @return {number}
*/
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
``````/**
* @param {number[]} nums
* @return {number}
*/
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
``````/**
* @param {number[]} nums
* @return {number}
*/
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 = [];

/**
* @param Integer[] \$nums
* @return Integer
*/
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
{
/**
* @param Integer[] \$nums
* @return Integer
*/
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
{
/**
* @param Integer[] \$nums
* @return Integer
*/
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:
# No more houses left to examine.
if i >= len(nums):
return 0

# Return cached value.
if i in self.memo:
return self.memo[i]

# Recursive relation evaluation to get the optimal answer.
ans: int = max(self.robFrom(i + 1, nums), self.robFrom(i + 2, nums) + nums[i])

# Cache for future use.
self.memo[i] = ans
return ans
``````
##### Dynamic Programming
``````class Solution:
def rob(self, nums: list[int]) -> int:
# Special handling for empty case.
if not nums:
return 0

N: int = len(nums)
maxRobbedAmount: list[int | None] = [None for _ in range(N + 1)]

# Base case initialization.
maxRobbedAmount[N], maxRobbedAmount[N - 1] = 0, nums[N - 1]

# DP table calculations.
for i in range(N - 2, -1, -1):

# Same as recursive solution.
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:

# Special handling for empty case.
if not nums:
return 0

N: int = len(nums)

rob_next_plus_one: int = 0
rob_next: int = nums[N - 1]

# DP table calculations.
for i in range(N - 2, -1, -1):

# Same as recursive solution.
current: int = max(rob_next, rob_next_plus_one + nums[i])

# Update the variables
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
}
}
``````