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

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

要求：

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

shuaidi

更新于 3 年前 196 10

共以下 10 个回答

hi 普通 2023年12月16日下午5:46

定义好dp 所代表的含义，然后通过递归得到转移方程

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

        int n = nums.size();
        vector<int> dp(n); //打劫到该家能获取的最大价值
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

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

        return dp[n - 1];
    }
};

0 赞同 0 条回复

June 普通 2023年11月15日下午4:41

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

0 赞同 0 条回复

桎梏普通 2023年9月17日上午9:50

class Solution {
    public int rob(int[] nums) {
        //dp[i] 截止第i个房间可获得的最高金额
        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]);
        // dp[2] = max(dp[0]+dp[2], dp[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年9月13日上午10:46

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

    public int dfs(int i,int[] nums) {
        if(i<0) return 0;
        if(cache[i]!=-1) return cache[i];
        int res = Math.max(dfs(i-1,nums), dfs(i-2,nums)+nums[i]);
        cache[i] = res;
        return res;
    }
}

递归：从上到下
递推：从下到上

0 赞同 0 条回复

Marshan 普通 2023年9月5日下午8:00

以前做过,想出来了

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        // dp[i]表示到下标i,能偷的最大金额
        vector<int> dp(n,0);

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

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

        return dp[n-1];
    }
};

0 赞同 0 条回复

人生何处不青山普通 2023年8月22日下午11:51

dp[i]表示以第i家之前可以偷的最大钱数

function rob(nums: number[]): number {
    let dp = new Array(nums.length).fill(0);
    dp[0] = nums[0]; 
    for (let i = 1; i < nums.length; i++) {
        let right = i >= 2 ? dp[i - 2] : 0;
        dp[i] = Math.max(dp[i-1],right + nums[i]);
    }
    return dp[nums.length - 1];
};

0 赞同 0 条回复

Mby 普通 2023年8月21日下午5:04

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

0 赞同 0 条回复

阿尚普通 2023年8月10日下午9:02

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int n = nums.length;
        //dp：考虑偷或者不偷第i个房间的最大收益
        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 - 1], dp[i - 2] + nums[i]);
        }

        return dp[n - 1];
    }
}

0 赞同 0 条回复

NullPointerException 普通 2023年8月10日下午8:30
class Solution {
public int rob(int[] nums) {
//从第四间开始考虑 -2 -3
int dp[]=new int[nums.length+1];
dp[0]=0;
dp[1]=nums[0];
if(nums.length1) return dp[1];
dp[2]=nums[1];
if(nums.length2)
return Math.max(dp[1],dp[2]);
int max = Math.max(dp[1],dp[2]);
for(int i=3;i<=nums.length;i++)
{
dp[i]=Math.max(dp[i-2]+nums[i-1],dp[i-3]+nums[i-1]);
max =Math.max(dp[i],max);
}
return max;
```
}
```
}
0 赞同 0 条回复

登录以回复

长河呼叫黄江普通 2023年8月9日下午11:24

8.9 周三
Day30：下面是代码

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        //因为dp[0] = 0，dp数组长度为n+1
        int[] dp= new int[n + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i <= n; i++){
            //dp[i]数组的最后一个是nums[i-1]
            dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);
        }
        return dp[n];
    }
}

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

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

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复