【Day 55 】2022-12-25 - 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

[whoam-challenge]

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

# 子问题：
# f(k) = 偷 [0..k) 房间中的最大金额

# f(0) = 0
# f(1) = nums[0]
# f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }

N = len(nums)
dp = [0] * (N+1)
dp[0] = 0
dp[1] = nums[0]
for k in range(2, N+1):
    dp[k] = max(dp[k-1], nums[k-1] + dp[k-2])
return dp[N]

[steven72574]

思路：动态规划

class Solution {
    public int rob(int[] nums) {

        int n = nums.length;
        if(n == 1)return nums[0];

        int[] dp = new int[n];//表示前i个房屋能偷到的最高金额
        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];

    }
}

[mayloveless]

思路

动态规划，状态转移方程：二维状态表记录当前index，偷和不偷两种情况，所能得到的最大金额

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    let n = nums.length
    if (n == 0) {
        return 0 
    }
    const dp = Array(n).fill(0).map(() => Array(2).fill(0))
    dp[0][0] = 0;// 不偷
    dp[0][1] = nums[0];// 偷
    for (let i=1;i<nums.length;i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);// 上一个偷不偷都可以
        dp[i][1] = dp[i-1][0]+nums[i];// 上一个不能偷
    }

    return Math.max(dp[n-1][0], dp[n-1][1]);
};

复杂度

时间：O(n) 空间：O(n) 可优化为O(1)

[chenming-cao]

解题思路

动态规划。用maxAmt[i]来记录选择第i个房子作为最后偷窃的房子时能偷窃到的最高金额，那么在第i个房子之前，小偷只能偷第(i - 2)或者(i - 3)个房子，状态转移方程为maxAmt[i] = max(maxAmt[i - 3] + nums[i], maxAmt[i - 2] + nums[i])，其中i > 2。对于i = 1和i = 2我们分别讨论，i = 1时为nums[0], i = 2时为max(nums[0], nums[1])。

代码

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        // base cases
        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0], nums[1]);
        // use an array to store the maxAmt when robbing the ith house as the last one
        int[] maxAmt = new int[n];
        // inital states, when n >= 3
        maxAmt[0] = nums[0];
        maxAmt[1] = nums[1];
        maxAmt[2] = nums[0] + nums[2];
        for (int i = 3; i < n; i++) {
            // if the ith house is to be robbed, then (i-1)th house must not be robbed. Only choices are robbing (i - 2)th house or (i - 3)th house as previous last house, because they are not adjacent to the ith house
            maxAmt[i] = Math.max(maxAmt[i - 3] + nums[i], maxAmt[i - 2] + nums[i]);
        }
        // the maximum amount could be either choosing the last house or the second last house as the last robbing target
        return Math.max(maxAmt[n - 2], maxAmt[n - 1]);
    }
}

复杂度分析

• 时间复杂度：O(n)，n为数组长度
• 空间复杂度：O(n)，因为用数组储存之前结果，可以优化到O(1)

[bookyue]

code

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

[snmyj]

class Solution {
public:
    int rob(vector<int>& nums) {
        int maxl=0;

        int n=nums.size();
        if(n==1) return nums[0];
        int maxr=0,max;
        if(n==2 && maxr>maxl) return nums[1];
        if(n==2 && maxr<maxl) return nums[0];

        for(int i=0;i<n;i++){
            int curval=nums[i]+maxl;
            if(curval>maxr) {
                max=curval;
                maxl=maxr;
                maxr=max;

            }
            else{
                max=maxr;
                maxl=maxr;

            }

        }

     return max;
    }
};

[Alyenor]

function rob(nums: number[]): number {
    const n=nums.length
    let f=new Array(n+1).fill(0),g=new Array(n+1).fill(0)
    for(let i=1;i<=n;i++){
        f[i]=g[i-1]+nums[i-1]
        g[i]=Math.max(f[i-1],g[i-1])
    }
    return Math.max(f[n],g[n])
};

[zywang0]

class Solution {
    public int rob(int[] nums) {

        int n = nums.length;
        if(n == 1)return nums[0];

        int[] dp = new int[n];//表示前i个房屋能偷到的最高金额
        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];
    }
}

[RestlessBreeze]

思路

动态规划

代码

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

复杂度

时间:o(n) 空间:o(1)

[tiandao043]

class Solution {
public:
    int rob(vector<int>& nums) {
        int f1=0,f2=0;
        for(int i=0;i<nums.size();i++){
            int f0=max(f1+nums[i],f2);f1=f2; 
            f2=f0;                       
        }
        return f2;
    }
};

[klspta]

class Solution {
    public int rob(int[] nums) {

        if(nums == null || nums.length == 0){
            return 0;
        }

        int N = nums.length;
        if(N == 1){
            return nums[0];
        }
        if(N == 2){
            return Math.max(nums[0], nums[1]);
        }

        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(Math.max(dp[i - 1], nums[i]), dp[i - 2] + nums[i]);
        }

        return dp[N - 1];
    }
}

[A-pricity]

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

[testplm]

class Solution(object):
    def rob(self, nums):
        length = len(nums)
        if length==0:
            return 0
        if length==1:
            return nums[0]
        if length==2:
            return max(nums)

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

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

        return max(dp)

[BruceZhang-utf-8]

思路

• 动态规划
• 由于不可以在相邻房屋偷窃，所以在当前n位置的房屋可以偷窃的最大值，要么就是n-1房屋可以偷窃的最大值，要么就是n-2位置房屋可偷窃的最大值加上当前房屋可偷窃的值，取最大值

关键点

代码

• 语言支持：Java

Java Code:

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

[Elon-Lau]

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

    size = len(nums)
    if size == 1:
        return nums[0]

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

    return dp[size - 1]

[saitoChen]

思路

dp[i]是下标i中偷取的最高金额 递推公式：连续的房子会报警，所以递推公式是dp[i] = Math.max((dp[i - 2] + nums[i]), dp[i - 1]) dp[i - 2] + nums[i]是因为如果偷i的话，那i - 1这个房子肯定不能偷；所以如果不偷i的话，就是取dp[i - 1]

代码

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

    return dp[lastIdx]
};

复杂度分析

时间复杂度：O(N) 康健复杂度：O(N)

[AtaraxyAdong]

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // 子问题：
        // f(k) = 偷 [0..k) 房间中的最大金额

        // f(0) = 0
        // f(1) = nums[0]
        // f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }

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

[Jetery]

198. 打家劫舍

思路

如果偷当前家, 就也偷取n - 2家, 不偷, 则考虑n - 1

代码 (cpp)

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return 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 - 2] + nums[i - 1], dp[i - 1]);
        }
        return dp[n];
    }
};

复杂度分析

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

[xuanaxuan]

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

思路

爬楼梯变形题

• 状态转移方程：用dp表示第i个房子能获取到的最高金额，dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1])
• 临界条件：dp(0)=nums[0]

let a = 0;
let b = 0;

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

return b;

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

复杂度

• 时间：O(N)

• 空间：O(1)

[paopaohua]

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

    }
}

[FlipN9]

/**
    TC: O(N)    SC: O(N)
*/
class Solution {
    public int rob(int[] nums) {
        int N = nums.length;
        int[] dp = new int[N + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        // 两个选择: 抢 or 不抢
        for (int i = 2; i <= N; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[N];
    }
}

[chiehw]

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

        vector<int> count = vector<int>(size, 0);
        count[0] = nums[0];
        count[1] = max(nums[0], nums[1]);

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

[Elsa-zhang]

if len(nums) == 1:
            return nums[0]

        dp = [0] * len(nums)
        dp[0], dp[1] = nums[0], 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]