【Day 55 】2022-02-04 - 198. 打家劫舍

[azl397985856]

198. 打家劫舍

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/house-robber/

前置知识

暂无

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

 

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 400

[CoreJa]

思路

不难看出下面两个dp思路都能解题，但前面一种明显更有时间色彩，而后面一种则更有跳脱出时空限制，局部最优找全局最优的感觉。

• DP：按照$dp[i]=max(dp[i-3],dp[i-2])+nums[i]$的思路，dp[i]表示从0开始到当前房子i且i必被打劫的情况下算最优解，复杂度$O(n)$
• DFS：回溯，TLE。就是想写着玩
• DFS+记忆化：上面的dfs改进一下就有了，复杂度$O(n)$
• DP：按照$dp[i]=max(dp[i-1],dp[i-2]+nums[i])$的思路，即从0开始到当前房子i的情况，当前房子i不一定打劫的情况，复杂度$O(n)$

代码

class Solution:
    # DP：按照$dp[i]=max(dp[i-3],dp[i-2])+nums[i]$的思路，`dp[i]`表示从0开始到当前房子`i`且`i`必被打劫的情况下算最
    # 优解，复杂度$O(n)$
    def rob1(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        elif n == 2:
            return max(nums[0], nums[1])
        dp = [nums[0], nums[1], nums[0] + nums[2]] + [0] * (n - 3)
        for i in range(3, n):
            dp[i] = max(dp[i - 3], dp[i - 2]) + nums[i]
        return max(dp[-1], dp[-2])

    # DFS：回溯，TLE。就是想写着玩
    def rob2(self, nums: List[int]) -> int:
        def dfs(i):
            if i < 0:
                return 0
            return max(dfs(i - 1), dfs(i - 2) + nums[i])

        return dfs(len(nums) - 1)

    # DFS+记忆化：上面的dfs改进一下就有了，复杂度$O(n)$
    def rob3(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [-1] * n

        def dfs(i):
            if i < 0:
                return 0
            if dp[i] != -1:
                return dp[i]
            dp[i] = max(dfs(i - 1), dfs(i - 2) + nums[i])
            return dp[i]

        return dfs(n - 1)

    # DP：按照$dp[i]=max(dp[i-1],dp[i-2]+nums[i])$的思路，即从0开始到当前房子`i`的情况，当前房子`i`不一定打劫的情况，
    # 复杂度$O(n)$
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [nums[0], max(nums[0], nums[1])] + [0] * (n - 2)
        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        return dp[-1]

[yetfan]

思路 dp 和昨天可以说是一个题了

代码

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) > 1:
            nums[1] = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            nums[i] = max(nums[i-1], nums[i] + nums[i-2])
        return nums[-1]

复杂度 时间 O(n) 空间 O(1)

[zwx0641]

class Solution { public int rob(int[] nums) { if (nums.length < 1) { return nums[0]; } int[] dp = new int[nums.length]; dp[0] = nums[0]; // dp[1] = nums[1]; for (int i = 1; i < nums.length; i++) { if (i >= 2) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); } else { dp[i] = Math.max(dp[i - 1], nums[i]); } } return dp[dp.length - 1]; } }

[charlestang]

思路

动态规划。对于第 i 家来说，如果偷这家，则无法偷 i - 1 家，则只能偷 i - 2 家，如果不偷这家，则可以偷 i - 1 家。

所以 f(i) = max(f(i - 1), f(i - 2) + nums(i - 1))

代码

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n + 1)
        dp[1] = nums[0]
        for i in range(2, n + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
        return dp[n]

时间复杂度 O(n)

空间复杂度 O(n)

[feifan-bai]

思路

1. DP

代码

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums: return 0
        n = len(nums)
        if n == 1:
            return nums[0]
        else:
            prev = nums[0]
            cur = max(prev, nums[1])
            for i in range(2, n):
                cur, prev = max(prev + nums[i], cur), cur
            return cur

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[zhiyuanpeng]

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums)
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[:2])
        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        return dp[-1]

time N space N

[wangzehan123]

Java Code:

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1)return nums[0];
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1]);
        }
        return dp[n-1];
    }
}

[Yrtryannn]

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }
}

[LannyX]

思路

DP

代码

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];

        if(n == 1){
            return nums[0];
        }
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for(int i = 2; i < n; i++){
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[zhangzz2015]

思路

• 标准的dp方法，在第i个房子，有两种选择，选择偷或者不偷，从两个里面选择对大。dp[i] = max(nums[i] + dp[i-2], dp[i-1])， 由于当前的状态之和前面的两个状态相关，可压缩。时间复杂度为O(n)，空间复杂度为O(1)。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int rob(vector<int>& nums) {

        //  dp[i] =   max(nums[i] + dp[i-2], dp[i-1]); 
        int prevPrev =0; 
        int prev = 0; 
        for(int i=0; i< nums.size(); i++)
        {
            int current = max(nums[i] + prevPrev, prev); 

            prevPrev = prev; 
            prev = current; 
        }

        return prev; 

    }
};

[cszys888]

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp_l2 = nums[0]
        dp_l1 = max(nums[0], nums[1])
        for idx in range(2, n):
            dp_new = max(dp_l2 + nums[idx], dp_l1)
            dp_l2 = dp_l1
            dp_l1 = dp_new
        return max(dp_l1, dp_l2)

time complexity: O(N) space complexity: O(1)

[falconruo]

思路:

动态规划 方法一、 数组dp存放前i个房子所能抢到的最大钱数 对于第i个房子，有两种选择，选择偷或者不偷，从两个里面选择对大。dp[i] = max(nums[i] + dp[i-2], dp[i-1])

方法二、优化 由于当前的状态之和前面的两个状态相关，可压缩为使用两个变量记录前i - 1和前i - 2个房子所能抢到的钱数

复杂度分析：

方法一、

• 时间复杂度: O(N)，其中N是房子数
• 空间复杂度: O(N)

方法二、

• 时间复杂度: O(N)，其中N是房子数
• 空间复杂度: O(1)

代码:

方法一、
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();

        if (n <= 1) return n == 0 ? 0 : nums[0];

        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = nums[0];

        for (int i = 2; i <= n; i++)
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);

        return dp[n];
    }
};

方法二、
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();

        if (n <= 1) return n == 0 ? 0 : nums[0];

        int oddMoney = 0, evenMoney = 0;

        for (int i = 0; i < n; i++) {
            int money = max(oddMoney, evenMoney + nums[i]);
            evenMoney = oddMoney;
            oddMoney = money;
        }

        return oddMoney;
    }
};

[LinnSky]

思路

动态规划

代码

     var rob = function(nums) {
        const len = nums.length
        if(len == 0) return 0
        const dp = new Array(len + 1)
        dp[0] = 0
        dp[1] = nums[0]
        for(let i = 2; i <= len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1])
        }
        return dp[len]
    };

复杂度分析

• 时间复杂度 O(N)
• 空间复杂度 O(N)

[Toms-BigData]

【Day 55】198. 打家劫舍

思路

dp换皮题

golang代码

func rob(nums []int) int {
    if len(nums) == 0{
        return 0
    }
    if len(nums) == 1{
        return nums[0]
    }
    var max func(a,b int) int
    max = func(a, b int) int {
        if a>b{
            return a
        }
        return b
    }
    if len(nums) == 2{
        return max(nums[0], nums[1])
    }
    dp:=make([]int , len(nums)+2)
    dp[0] = nums[0]
    dp[1] = nums[1]
    dp[2] = nums[0]+nums[2]
    for i:=3;i<len(dp);i++{
        dp[i] = max(dp[i-3],dp[i-2])
        if i<len(nums){
            dp[i] +=nums[i]
        }
    }
    return max(dp[len(dp)-2], dp[len(dp)-1])
}

复杂度

时间:O(n) 空间:O(n)

[Tesla-1i]

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums)
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[:2])
        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        return dp[-1]

[ZacheryCao]

Idea

Dynamic Programming

Code

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()<1) return 0;
        if(nums.size()<2) return nums.front();
        int n = nums.size();
        int dp0 = nums[n-1], dp1 = nums[n-2];
        for(int i = n-3; i>=0;i--){
            int cur = max(dp0+nums[i], dp1);
            dp0 = max(dp0, dp1);
            dp1 = cur;
        }
        return max(dp0, dp1);
    }
};

Complexity:

Time: O(N) Space: O(1)

[yan0327]

func rob(nums []int) int {
    a,b:=0,0
    for i:=0;i<len(nums);i++{
        temp := b
        b = max(a+nums[i],b)
        a = temp
    }
    return b
}
func max(a, b int) int{
    if a > b{
        return a
    }else{
        return b
    }
}

[moirobinzhang]

Code:

public int Rob(int[] nums) {
    if (nums == null || nums.Length == 0)
        return 0;

    if (nums.Length == 1)
        return nums[0];

    int[] dp = new int[nums.Length + 1];
    dp[0] = nums[0];
    dp[1] = Math.Max(nums[0], nums[1]);

    for (int i = 2; i < nums.Length; i++)
        dp[i] = Math.Max(nums[i] + dp[i - 2], dp[i - 1]);

    return dp[nums.Length - 1];

}

[zwmanman]

class Solution(object): def rob(self, nums): """ :type nums: List[int] :rtype: int """ length = len(nums)

    if length == 1:
        return nums[0]

    prev = nums[0]
    curr = max(prev, nums[1])

    for i in range(2, length):
        curr, prev = max(prev + nums[i], curr), curr

    return curr

[Aobasyp]

思路 动态规划

class Solution { public: int rob(vector& nums) { if (nums.empty()) return 0; auto sz = nums.size(); if (sz == 1) return nums[0]; auto prev = nums[0]; auto cur = max(prev, nums[1]); for (auto i = 2; i < sz; ++i) { auto tmp = cur; cur = max(nums[i] + prev, cur); prev = tmp; } return cur; } };

时间复杂度：O(N) 空间复杂度：O(1)

[dahaiyidi]

Problem

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

---

Note

---

Complexity

• 时间O：n
• 空间O：1

---

Python

C++

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1){
            return nums[0];
        }

        int ppre = nums[0];
        int pre = max(nums[0], nums[1]);
        int res = -1;
        for(int i = 2; i < nums.size(); i++){
            int tmp = ppre;
            ppre = pre;
            pre = max(tmp + nums[i], pre); // 使用i，或者不是用i
        }
        return pre;
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[xuhzyy]

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        return dp[-1]

[simbafl]

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n + 1)
        dp[1] = nums[0]
        for i in range(2, n + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
        return dp[n]

[Richard-LYF]

class Solution: def rob(self, nums: List[int]) -> int: if len(nums)<2: return nums[0] dp = [0] * len(nums)

    dp[0] = nums[0]
    dp[1] = max(nums[0],nums[1])

    for i in range(2,len(nums)):
        dp[i] = max(dp[i-1],dp[i-2] + nums[i])

    return dp[-1]

on on

[Tao-Mao]

Idea

DP. Edge case 1: when there's no house. Edge case 2: when there's only one house.

Code

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        int[] res = new int[nums.length+1];
        res[0] = 0;
        res[1] = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            res[i+1] = Math.max(res[i-1] + nums[i], res[i]);
        }
        return res[nums.length];
    }
}

Complexity

Space: O(n) Time: O(n)

[jiaqiliu37]

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = [0]*len(nums)
        dp[0] = nums[0]
        if len(nums) == 1:
            return dp[0]
        dp[1] = nums[1]

        for i in range(2, len(nums)):
            if i == 2:
                dp[i] = dp[0] + nums[2]
            else:
                dp[i] = max(dp[i - 2], dp[i - 3]) + nums[i]

        return max(dp[-1], dp[-2])

Time complexity O(n) Space complexity O(n)

[haixiaolu]

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0

        #[rob1, rob2, n, n + 1, ...]
        for n in nums:
            temp = max(n + rob1, rob2)
            rob1 = rob2
            rob2 = temp 
        return rob2

时间复杂度：

• Time: O(n)
• Space: O(1)

[tongxw]

思路

dp(i) 打劫前i个房子的钱， dp(i) = max(dp(i-1), dp(i-2) + nums[i-1]) dp(0) = 0, dp(1) = nums[0] 滚动数组优化空间

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[3];
        dp[1] = nums[0];
        for (int i=2; i<=n; i++) {
            dp[i%3] = Math.max(dp[(i-2) % 3] + nums[i - 1], dp[(i-1) % 3]);
        }

        return dp[n % 3];
    }
}

TC: O(n) SC: O(1)

[z1ggy-o]

思路

动态规划。DFS 回溯应该也可以解。题目分析后可变为：针对当前房屋，我们要不要偷左侧相邻的那一间。

代码

CPP

class Solution {
public:
    int rob(vector<int>& nums) {
        // 1. one house => one
        // 2. two house => max of the two
        // 3. three house => max(curr + max_prev_2, max_prev_1)
        // 4. four house => max(curr + max_prev_2, max_prev_1)

        int nr_house = nums.size();
        if (nr_house == 0) return 0;
        if (nr_house == 1) return nums[0];

        int one_before = max(nums[0], nums[1]);
        int two_before = nums[0];
        int curr = 0;
        for (int i = 2; i < nr_house; i++) {
            curr = max(nums[i] + two_before, one_before);
            two_before = one_before;
            one_before = curr;
        }
        return one_before;
    }
};

复杂度分析

• 时间：O(n)，遍历了一次 array
• 空间：O(1)，只存放了前两个状态的值

[li65943930]

var rob = function (nums) { // Tag: DP const dp = []; dp[0] = 0; dp[1] = 0;

for (let i = 2; i < nums.length + 2; i++) { dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1]); }

return dp[nums.length + 1]; };

[Myleswork]

思路

dp

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if(len == 1) return nums[0];
        if(len == 2) return max(nums[0],nums[1]);
        int dp[len+1];
        dp[0] = 0;
        dp[1] = nums[0];
        dp[2] = nums[1];
        int res = max(dp[1],dp[2]);
        for(int i = 2;i<len;i++){
            dp[i+1] = max(dp[i-1],dp[i-2]) + nums[i];
            res = max(res,dp[i+1]);
        }
        return res;
    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

[for123s]

class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        int dp1 = nums[0];
        int dp2 = len>1?max(nums[1],dp1):dp1;
        for(int i=2;i<len;i++)
        {
            int temp = dp2;
            dp2 = max(dp2,dp1+nums[i]);
            dp1 = temp;
        }
        return dp2;
    }
};

[kbfx1234]

198. 打家劫舍

// 2-4
class Solution {
public:
    int rob(vector<int> & nums) {
        int curr = 0, prev = 0;

        //curr表示dp[k-1] 偷到当前为止最大金额
        for (int i : nums){
            int temp = max(curr, prev + i);
            prev = curr;
            curr = temp;
        }
        return curr;
    }
};

[zol013]

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return nums[0]
        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[1], dp[0])
        for i in range(2, len(nums)):
            dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])

        return dp[-1]

[baddate]

int rob(vector<int>& nums) {
    int prev = 0;
    int curr = 0;
    for (int i : nums) {
        int temp = max(curr, prev + i);
        prev = curr;
        curr = temp;
    }
    return curr;
}

[Moin-Jer]

思路

---

动态规划

代码

---

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}

复杂度分析

---

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[ZJP1483469269]

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n + 1)
        for i in range(1 ,n + 1):
            dp[i] = max(dp[i-1] , dp[i-2] + nums[i - 1])

        return dp[-1]

[JudyZhou95]

代码

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0

        prev_prev = 0
        prev = 0

        for i in nums:
            now = max(prev_prev + i, prev) #best solution for current position
            prev_prev = prev #best solution for last position
            prev = now

        return now

思路

计算当前位置最大收入的时候，有两个选择偷当前的和不偷当前的。如果偷当前的，那么总收入就是prev_prev收入+当前财产。如果没有偷当前的，那么总收入就和prev的收入一样多。在两者中选大的那个作为当前最大收入。按照这样的逻辑遍历房子，每次都保存当前最大收入和前一个位置的最大收入，供计算下一个位置使用。\ Time Complexity: O(N)\ Space Complexity: O(1)

[alongchong]

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}

[ginnydyy]

Problem

https://leetcode.com/problems/house-robber/

Notes

• Typical DP problem
• Need to figure out how to make decision at the ith house. The point is decide to rob or not rob the ith house.
• Think about:
  • if rob it, the max profit is the current house's value + the max profit when going to the next next house.
  • if not rob it, the max profit is the max profit when going to the next house.
• Once figuring out the sub problems' relation. Need to figure out the base condition.
  • since we need to get the max profit when starting at the 0th house, dp[0] is our result.
  • the base conditions are about the other end of the dp, i.e. dp[n] and dp[n - 1].
  • dp[n] means the max profit when stopping at the nth house, since there is no nth house, the max profit is 0.
  • dp[n - 1] means the max profit when stopping at the n - 1th house, since if there is only one house, and no other houses in next steps, must rob it to gain the max profit, the max profit is nums[n - 1].
• Having the sub problem relation and base conditions, just iterate the houses, and fulfill the dp, return the dp[0].

Solution

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[n] = 0; // no house to rob
        dp[n - 1] = nums[n - 1]; // if there is only this house, since no next house, must rob it to make max profit
        for(int i = n - 2; i >= 0; i--){
            dp[i] = Math.max(dp[i + 1], dp[i + 2] + nums[i]); // make decision to rob or not rob the current ith house
        }
        return dp[0];
    }
}

• Optimize space

  class Solution {
  public int rob(int[] nums) {
      // base conditions
      int n = nums.length;
      int next1 = nums[n - 1];
      int next2 = 0;
  
      for(int i = n - 2; i >= 0; i--){
          int cur = Math.max(next1, nums[i] + next2);
          next2 = next1;
          next1 = cur;
      }
  
      return next1;
  }
  }

Complexity

• Time: O(n). n is the length of the input nums array.
• Space: O(n). n is the length of the input nums array. The extra space is for the dp array. To optimize it, can use two variables to store the next two max profit, and the cost would be O(1).

[hx-code]

const rob = nums => { // 数组长度 const len = nums.length; // dp数组初始化 const dp = [nums[0], Math.max(nums[0], nums[1])]; // 从下标2开始遍历 for (let i = 2; i < len; i++) { dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); } return dp[len - 1]; };

[CodingProgrammer]

思路

DP

• dp[i] 表示抢到第 i 间房的最大收益。
• 递推公式：dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]) 。抢到第 i 间房的最大收益为不抢第 i 间房的最大收益(dp[i - 1]) 或者 抢第 i 间房的最大收益(dp[i - 2] + nums[i]))

代码

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException();
        }
        int length = nums.length;
        if (length < 2) return nums[0];
        // dp[i] 表示抢到第 i 间房间时的最大收益
        // dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[length - 1];
    }
}

复杂度

• Time : O(N)
• Space: O(N)

压缩数组, 额外空间复杂度 O(1)

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException();
        }
        int length = nums.length;
        if (length < 2) return nums[0];
        // dp[i] 表示抢到第 i 间房间时的最大收益
        // dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
        int dp = Integer.MIN_VALUE, dp1 = nums[0], dp2 = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp = Math.max(dp1 + nums[i], dp2);
            dp1 = dp2;
            dp2 = dp;
        }
        return dp2;
    }
}

[xianxianxianyu]

hard 唯唯诺诺 橙题随便乱杀（bushi

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        int size = nums.size();
        if (size == 1) {
            return nums[0];
        }
        vector<int> dp = vector<int>(size, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[size - 1];
    }
};

[spacker-343]

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        if (len == 1) {
            return dp[0];
        }
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]); 
        }
        return dp[len - 1];
    }
}

[1149004121]

198. 打家劫舍

思路

动态规划。

代码

var rob = function(nums) {
    let a = 0, b = 0;
    const n = nums.length;
    for(let i = 0; i < n; i++){
        let temp = b;
        b = Math.max(b, a + nums[i]);
        a = temp;
    };
    return b;
};

复杂度分析

• 时间复杂度：O(N)。
• 空间复杂度：O(1)。

[hdyhdy]

思路： 动态规划，抢劫当前位置的时候小偷抢到的钱是这个位置的钱加上上上个位置的时候有的钱以及上上上个为位置有的钱之间的最大值。

func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    ans := max(nums[0],nums[1])

    for i := 2 ; i < len(nums); i ++ {
        if i == 2 {
            nums[i] += nums[0] 
        }else {
            nums[i] += max(nums[i-2],nums[i-3])
        }
        ans = max(ans,nums[i])
    } 
    return ans 
}

func max(i,j int) int {
    if i > j {
        return i
    }else {
        return j
    }
}

时间复杂度：O(n) 空间复杂度：O（1）

[GaoMinghao]

思路

比较简单的动态规划，每一个节点的选择取决于前一个节点有没有选，有选择的话，则当前节点必不能选，没有选择的话，则在前两个的基础上加上当前节点的值，二者取大值

代码

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1)
            return nums[0];
        if(nums.length == 2)
            return Math.max(nums[0],nums[1]);
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2;i < nums.length;i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
        }
        return dp[nums.length-1];
    }
}

复杂度

时间复杂度O(n)

[junbuer]

思路

• 动态规划 对于第i家存在两种情况偷则不能偷其前一家，不偷则可以偷前一家 则有状态转移方程：$dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 2])$

  class Solution(object):
  def rob(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      n = len(nums)
      if n == 1:
          return nums[0]
      if n == 2:
          return max(nums)
      a = nums[0]
      b = max(nums[0], nums[1])
      i = 2
  
      while n - 2:
          c = max(b, a + nums[i])
          a = b
          b = c
          i += 1
          n -= 1
      return c

  复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

[shamworld]

var rob = function(nums) {
    if(!nums.length) return 0;
    const len = nums.length;
    let dp = new Array(len+1);
    dp[0] = 0;
    dp[1] = nums[0];
    for(let i = 2; i <= len;i++){
        dp[i] = Math.max(dp[i-2]+nums[i-1],dp[i-1]);
    }
    return dp[len];
};

[HondryTravis]

思路

动态规划

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  if (nums.length === 0 || nums === null) return 0
  if (nums.length === 1) return nums[0]

  const { max } = Math, n = nums.length
  const dp = new Array(n)

  // 初始化的时候，如果只有两间房，所以要给定初始值
  // 计算 dp[0] dp[1] = max(dp[0], nums[1])
  dp[0] = nums[0]
  dp[1] = max(nums[0], nums[1])

  for (let i = 2; i < n; i ++) {
    // 为什么要和前一天比较，是因为前一天已经计算过了
    // 当前这次的金额来自于 dp[i - 2] + nums[i]
    // 前一天能够偷到的最大金额 dp[i - 1]
    // 所以有 max(dp[i - 1], dp[i - 2] + nums[i])
    dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  }
  return dp[n - 1]
};

复杂度分析

时间复杂度 O(n)

空间复杂度 O(1)