【动态规划专题】LeetCode 198. 打家劫舍

本问题对应课程链接：剑指offer刷题第三期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 3 年前 95 12

共以下 12 个回答

招舟子普通 2024年1月3日下午4:32
class Solution {
public int rob(int[] nums) {
if(nums.length1){
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];
}
```
}
啊
0 赞同 0 条回复

登录以回复
九号球普通 2023年12月7日上午8:39

“`java
class Solution {
public int rob(int[] nums) {
//假设最大方案是以i结尾的房屋，则dp[i] = max(dp[i-2], dp[i-3])
int res = 0;
int length = nums.length;
if (length == 1) {
return nums[0];
}
if (length == 2) {
return Math.max(nums[0], nums[1]);
}
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = nums[1];
dp[2] = nums[0] + nums[2];
res = Math.max(dp[2], dp[1]);
for (int i = 3; i < length; i++) { dp[i] = Math.max(dp[i - 2], dp[i - 3]) + nums[i]; res = Math.max(res, dp[i]); } return res; } }

0 赞同 0 条回复

登录以回复

mpweixin用户永久会员 2023年7月25日上午11:22

class Solution {
//时间O(n) 空间O(n)
    public int rob(int[] nums) {

        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = nums[0];

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

        return dp[nums.length];

    }
}

0 赞同 0 条回复

张开怀普通 2023年7月24日下午7:41

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)

0 赞同 0 条回复

Dsjh 普通 2023年7月24日上午10:48

MY

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

0 赞同 0 条回复

花老爷普通 2023年7月23日下午4:31

动态规划
时间：O(n)
空间：O(1)

class Solution {
    public int rob(int[] nums) {
        int pre = 0, cur = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int temp = Math.max(pre + nums[i], cur);
            pre = cur;
            cur = temp;
        }
        return cur;
    }
}

0 赞同 0 条回复

怀瑾永久会员 2023年7月23日下午3:53
C++实现

“`C++
class Solution {
public:
int rob(vector& nums) {
int pprev = nums[0];
if (nums.size() == 1) return pprev;
int prev = max(pprev, nums[1]);
if (nums.size() == 2) return prev;
```
    int result;
    for (int i = 2; i < nums.size(); i++) {
        result = max(pprev + nums[i], prev);
        pprev = prev; prev = result;
    }
    return result;
}
```
};

“`
0 赞同 0 条回复

登录以回复

Vow the vow。普通 2023年7月23日上午11:02

时间复杂度:O(n)，空间复杂度O(n)

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

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月23日上午5:02

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

        return dp[len(nums) - 1]

可用两个变量优化

0 赞同 0 条回复

BOZ 普通 2023年7月22日下午5:44

【思路】DP，dp[i]为在0～i房屋中能偷窃到的最大金额
【复杂度】时间O(n)，空间O(1)

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

        int result;
        for (int i = 2; i < nums.size(); i++) {
            result = max(pprev + nums[i], prev);
            pprev = prev; prev = result;
        }
        return result;
    }
};

0 赞同 0 条回复

yxy 普通 2023年7月22日下午5:43

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

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

0 赞同 0 条回复

Yodl. 普通 2023年7月22日下午5:17

class Solution {
public:
    int rob(vector<int>& nums) {//空间复杂度O(n)
        if(nums.size()==1)
        {
            return nums[0];
        }
        int dp[nums.size()];
        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];
    }
    // int rob(vector<int>& nums)//空间复杂度O(1)
    // {
    //     int prev = 0;
    //     int curr = 0;
    //     // 每次循环，计算“偷到当前房子为止的最大金额”
    //     for (int i : nums)
    //     {
    //         // 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
    //         // dp[k] = max{ dp[k-1], dp[k-2] + i }
    //         int temp = max(curr, prev + i);
    //         prev = curr;
    //         curr = temp;
    //         // 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
    //     }

    //     return curr;
    // }
};

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【动态规划专题】LeetCode 198. 打家劫舍

共以下 12 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复