【Day 55 】2023-04-09 - 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

[tzuikuo]

思路

动态规划，不能相邻。dp[i]的含义是前i间房子偷最多。两种情况，是否偷第i间。

代码

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

        return dp[n-1];
    }
};

复杂度分析

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

[Meisgithub]

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

[kofzhang]

思路

动态规划，当前房屋累计结果应该等于前前个房屋的累计结果+当前房屋的钱数 或是 前面房间的累计结果。即dp[i]=max(dp[i-2]+nums[i],dp[i-1])

复杂度

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

代码

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

[NorthSeacoder]

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const n = nums.length;
    if (n < 2) return nums[0];
    //前 n 个房屋能够偷到的最高金额
    const dp = [];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    //dp[i]= Math.max(dp[i-1],dp[i-2]+nums[i]);
    for (let i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp.at(-1);
};

• TC:O(n)
• SC:O(n)

[JiangyanLiNEU]

• DP
• T = O(N)
• S = O(1)

  class Solution(object):
  def rob(self, nums):
      if len(nums) == 1: return nums[0]
      prev_two, prev_one = nums[0], max(nums[0], nums[1])
      for i in range(2, len(nums)):
          prev_two, prev_one = prev_one, max(prev_two+nums[i], prev_one)
      return prev_one

[Diana21170648]

思路

动态规划

代码

class Solution: def robmaxmoneys(self, robnums:list[int]) -> int:

   # dp=[0]*(len(robnums)+1)
    if not robnums :
        return 0
    length=len(robnums)
    if length==1:
        return robnums[0]
    else:
        previous=robnums[0]
        current=max(previous,robnums[1])
        for i in range(2, length):
        #dp[i] = max(previous+num[i], current) ,current)
            previous,current= max(previous+robnums[i], current) ,current
    #return dp[-1]
    return current

（此处撰写代码）

**复杂度分析**
- 时间复杂度：O(N)，其中 N 为数组长度。
- 空间复杂度：O(1)，只需要保存current和previous

[Abby-xu]

class Solution:
    def rob(self, nums: List[int]) -> int:
        # Base Case: nums[0] = nums[0]
        # nums[1] = max(nums[0], nums[1])
        # nums[k] = max(k + nums[k-2], nums[k-1])
        '''
        # Approach 1:- Construct dp table - O(n) space
        if not nums: return 0
        if len(nums) == 1: 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(nums[i] + dp[i-2], dp[i-1])
        return dp[-1] # return the last element
        '''
        # Approach 2:- O(1) space
        prev = curr = 0
        for num in nums:
            temp = prev # This represents the nums[i-2]th value
            prev = curr # This represents the nums[i-1]th value
            curr = max(num + temp, prev) # Here we just plug into the formula
        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]

[wangzh0114]

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev = 0;
        int curr = 0;
        for (int i : nums) {
            // dp[k] = max{ dp[k-1], dp[k-2] + i }
            int temp = max(curr, prev + i);
            prev = curr;
            curr = temp;
        }
        return curr;
    }
};

[jmaStella]

思路

dp dp[i] 分两种情况 :

1. 偷房子i => nums[i] + dp[i-2]
2. 不偷房子i => dp[i-1] 两者取max

代码

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(dp[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];
    }

复杂度

时间 O(N) 空间 O(N)

[lp1506947671]

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

        length = len(nums)
        if length == 1:
            return nums[0]
        else:
            prev = nums[0]
            cur = max(prev, nums[1])
            for i in range(2, length):
                cur, prev = max(prev + nums[i], cur), cur
            return cur

复杂度分析

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

[bookyue]

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

    public int rob(int[] nums) {
        int prev = 0;
        int secPrev = 0;
        int ans = 0;
        for (int num : nums) {
            ans = Math.max(secPrev + num, prev);
            secPrev = prev;
            prev = ans;
        }

        return ans;
    }

[harperz24]

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

        tab = [0] * len(nums)
        tab[0] = nums[0]
        tab[1] = max(nums[0], nums[1])

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

        # time: O(n)
        # space: O(n)

[zhangyu1131]

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

        //dp[i]表示抢到第i个房子时最多能掠夺的数量
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        dp[1] = nums[1] > nums[0] ? nums[1] : nums[0];

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

        return dp.back();
    }
};

[Hughlin07]

class Solution {

public int rob(int[] nums) {

    int rob = 0, notrob = 0;
    for(int x: nums){
        int temp = rob;
        rob = notrob + x;
        notrob = temp;
    }

    return Math.max(rob, notrob);

}

}

[kangliqi1]

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

    length = len(nums)
    if length == 1:
        return nums[0]
    else:
        prev = nums[0]
        cur = max(prev, nums[1])
        for i in range(2, length):
            cur, prev = max(prev + nums[i], cur), cur
        return cur

[DragonFCL]

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];
};

[Lydia61]

198. 打家劫舍

思路

动态规划，max(curr, prev + i)

代码

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev = 0
        curr = 0
        for i in nums:
            prev, curr = curr, max(curr, prev + i)
        return curr

复杂度分析

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

[FireHaoSky]

思路：动态规划

代码：python

class Solution:
    def rob(self, nums: List[int]) -> int:
        pre = cur = 0
        for i in nums:
            pre, cur = cur, max(cur, pre+i)
        return cur

复杂度分析：

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

[RestlessBreeze]

code

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

[Fuku-L]

代码

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

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[chocolate-emperor]

class Solution {
public:
    //所有可能方案集合中的和最大值
    // 划分标准：最后一个元素为i， dp[0,1...n-1] 其中的最大值
    // dp[i] = dp[0...i-2] + nums[i]
    // strart:dp[0] = nums[0]   dp[1] = nums[1]
    // i belongs to [2,n-1]
    // max(dp[0..n-1])
int dp[100+4]={0};    
    int rob(vector<int>& nums) {
        int l = nums.size();
        if(l<=1)    return nums[0];

        dp[0] = nums[0];
        dp[1] = nums[1];
        for(int i = 2; i<l;i++){
            for(int j = 0; j<=i-2;j++){
                dp[i] = max(dp[i],dp[j] + nums[i]);
            }
        }
        int res = 0;
        for(int i=0; i<l; i++){
            res = max(res,dp[i]);
        }
        return res;
    }
};

[joemonkeylee]

思路

dp

代码

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

            int N = nums.Length;
            int[] dp = new int[N + 1];
            dp[0] = 0;
            dp[1] = nums[0];
            for (int k = 2; k <= N; k++)
            {
                dp[k] = Math.Max(dp[k - 1], nums[k - 1] + dp[k - 2]);
            }
            return dp[N];
        }

复杂度分析

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

[liuajingliu]

解题思路

动态规划

代码实现

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];
};

[bingzxy]

思路

动态规划

代码

class Solution {
    public int rob(int[] nums) {
        int preRobMax = 0, preNotRobMax = 0;
        for (int num : nums) {
            int curRobMax = preNotRobMax + num;
            int curNotRobMax = Math.max(preRobMax, preNotRobMax);
            preNotRobMax = curNotRobMax;
            preRobMax = curRobMax;
        }
        return Math.max(preNotRobMax, preRobMax);
    }
}

复杂度分析

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

[X1AOX1A]

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

        length = len(nums)
        if length == 1:
            return nums[0]
        else:
            prev = nums[0]
            cur = max(prev, nums[1])
            for i in range(2, length):
                cur = max(prev + nums[i], cur)
        prev = cur
            return cur

[yingchehu]

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

複雜度

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

[Jetery]

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

[JasonQiu]

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

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

[aoxiangw]

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            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]

time, space: O(n), O(n)

[snmyj]

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

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

         }
         return dp[nums.size()-1];
    }
};

[chanceyliu]

代码

function rob(nums: number[]): number {
  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)

[Zoeyzyzyzy]

class Solution {
    //Time Complexity: O(n), Space Complexity: O(n)
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return nums[0];
        int[] dp = new int[n + 1];
        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];
    }

    //Optimize the Space Complexity
    //Space Complexity: O(1)
    public int rob1(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return nums[0];
        int pre = nums[0];
        int cur = Math.max(pre, nums[1]);
        for (int i = 2; i < n; i++) {
            int temp = cur;
            cur = Math.max(pre + nums[i], cur);
            pre = temp;
        }
        return cur;
    }
}

[CruiseYuGH]

思路

关键点

代码

• 语言支持：Python3

Python3 Code:

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

复杂度分析

令 n 为数组长度。

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