azl397985856 commented 2 years ago

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

zhiyuanpeng commented 2 years ago

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

time O(N) space O(N)

Davont commented 2 years ago

/**
 * @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];
};

ShuqianYang commented 2 years ago


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

MichaelXi3 commented 2 years ago

Idea

DP_topToBottom
- This logic normally requires Recursion
- Image that you have robbed to the last house, then think backwards. In what sequence of robbing will you achieve the maximum money?
- Use recursion to display the logic, and use dp array (memo) to reduce the time complexity from O(n!) to O(n).

DP_bottomToTop

This logic usually uses Iteration
Image you are a robber that starts from the very first house, you rob houses in a normal sequence. In what sequence will you achieve the max amount of money.
dp array records the best possible money earned until i-th house. Use each round of iteration to maintain such a dp array, the answer will be the value at the last space of dp array.
Code
DP_topToBottom
```
class Solution {
```

int[] dp; // DP array records the best possible money earned until i-th house

public int rob(int[] nums) { int n = nums.length; // total number of houses dp = new int[n]; Arrays.fill(dp, -1);

return Rob(nums, n - 1); // topToBottom logic, think from the last house

}

private int Rob(int[] nums, int i) { if (i < 0) { return 0;} // outOfBound situation

if (dp[i] >= 0) { return dp[i];} // Avoid repetitive computations

dp[i] = Math.max(Rob(nums, i - 2) + nums[i], Rob(nums, i - 1)); // Filling in dp array

return dp[i]; // Recursion ends, this is the value at dp[n-1], the max money robbed at the last house

} }

- DP_bottomToTop
```java
class Solution {

public int rob(int[] nums) {
    int[] dp = new int[nums.length + 1];
    dp[0] = 0; // Haven't start rob
    dp[1] = nums[0]; // Rob one house

    for (int i = 1; i < nums.length; i++) {
        // Current house value
        int val = nums[i]; 

        // You can either rob "curHouse + 上上个house" or rob "上一个house"
        dp[i+1] = Math.max(dp[i], dp[i-1] + val);
    }

    return dp[nums.length];
}
}

Complexity

DP_bottomToTop

Time O(N)
Space O(1)
DP_topToBottom
Time O(N)
Space O(N)

JiangWenqi commented 2 years ago

C++

Solution 1

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

Solution 2

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

Solution 3

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

KelvinG-LGTM commented 2 years ago

思路

当前房屋的最大价值 = max (不抢当前, 抢当前)

代码

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

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

        return cur

复杂度分析

时间复杂度

O(N)

空间复杂度

O(1)

MoonLee001 commented 2 years ago

思路

动态规划，滚动数组

代码

var rob = function(nums) {
    const n = nums.length;
    if (n == 0) {
        return 0
    } else if (n == 1) {
        return nums[0];
    }
    let p = nums[0];
    let q = Math.max(nums[0], nums[1]);
    for (let i = 2; i < n; i++) {
        const r = Math.max(q, p + nums[i]);
        p = q;
        q = r;
    }
    return q;
}

复杂度分析

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

Geek-LX commented 2 years ago

5.25

思路：动态规划

代码：

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)

KWDFW commented 2 years ago

Day55

198、打家劫舍

javascript #动态规划

思路

1、求最优解且每一步之间不会互相影响，故为动态规划

2、dp[i]:抢到i家的最大钱数,抢i家的话是dp[i-2]+nums[i]，不抢的话是dp[i-1]

3、故状态转移方程为：dp[i]=max(dp[i-2]+nums[i],dp[i-1])

4、当只有一间房屋时，直接抢：dp[0]=nums[0]，两间房屋时，抢最多的那个：dp[1]=max(nums[0],nums[1])

5、求出最优解

代码

var rob = function(nums) {
  const n=nums.length
  let dp=[]
  dp[0]=nums[0]
  dp[1]=Math.max(nums[0],nums[1])
  for(let i=2;i<n;i++){
    dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1])
    //状态转移方程
  }
  return dp[n-1]
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

zqwwei commented 2 years ago

Code

top down dp

class Solution {
    private int[] cache;

    private int robFrom(int i, int[] nums) {
        if (i >= nums.length) {
            return 0;
        }

        if (this.cache[i] > -1) {
            return this.cache[i];
        }

        int res = Math.max(robFrom(i + 1, nums), robFrom(i + 2, nums) + nums[i]);
        this.cache[i] = res;
        return res;
    }

    public int rob(int[] nums) {
        this.cache = new int[100];

        Arrays.fill(this.cache, -1);

        return robFrom(0, nums);
    }
}

houmk1212 commented 2 years ago

思路

动态规划

代码

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] = nums[1];
        if (n > 2) {
            dp[2] = dp[0] + nums[2];
        }

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

复杂度

时间复杂度：O（N）
空间复杂度：O（N）可以通过滚动数组优化到O（1）

Joyce94 commented 2 years ago

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

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

ghost commented 2 years ago

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

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

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

        return curr

wychmod commented 2 years ago

思路

动态规划

代码

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)

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

复杂度分析

时间复杂度On 空间复杂度On

TonyLee017 commented 2 years ago

思路

动态规划

代码

n = len(nums)
if n == 1: return nums[0]
first = nums[0]
second = max(nums[:2])
for i in range(2,n):
 temp = second
 second = max(second,first+nums[i])
 first = temp
return second

复杂度分析

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

ZacheryCao commented 2 years ago

Idea

DP

Code

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

Complexity:

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

hyh331 commented 2 years ago

Day55 思路

状态转移方程：dp[k]=max(dp[k-1] , dp[k-2] + nums[k-1] )

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==0){
            return 0;
        }
        int n=nums.size();
        //开辟一个大小为 n+1 数组，全为0
        vector<int> dp(n+1,0);
        dp[0]=0;
        dp[1]=nums[0];
        for(int k=2; k<=n; k++){
            dp[k]=max(dp[k-1], dp[k-2]+nums[k-1]);
        }
        return dp[n];
    }
};

复杂度分析

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

Ellie-Wu05 commented 2 years ago

动态规划

nums[i]表示每个房间存放的金额
dp[i] 表示到目前房间为止能够获得的最大数
我们需要比较dp[i-1] 和 dp[i-2]+nums[i]: 因为如果 dp[i-2]+nums[i] 是小于dp[i-1]的话，我们得不偿失，所以dp[i] = dp[i-1]，如果 dp[i-2]+nums[i] 是大于dp[i-1]的话，我们那就让dp[i] = dp[i-2]+nums[i]

代码

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

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

        return dp[n-1];
        }

    }

复杂度

时间：On 空间：On

优化

我们只需要三个数字
- dp[i],dp[i-1],dp[i-2]
`class Solution { public int rob(int[] nums) { int n = nums.length; int ppre = 0,pre = nums[0],current =nums[0];
```
for (int i =1; i<n;i++){
    current = Math.max(pre,ppre+nums[i]);
    ppre = pre;
    pre = current;
}

return current;
```
} } `

复杂度

时间 On 空间 O1

ShawYuan97 commented 2 years ago

思路

使用动态规划

最右子结构前i间房最大总金额
选择第i间房后，选择之后的房的金额不会影响前面的总金额
状态空间：dp[i]表示前i间房子的最大总金额
临界条件：0<=i<=n-1
状态转移方程：dp[i] = max(dp[j]+nums[i],dp[i]),0<=j<=i-2
枚举状态：双重循环
关键点

如何定义状态

如何使用滚动数组

代码

class Solution:
def rob(self, nums: List[int]) -> int:
    """
    不能选择相邻的房间，又要保证总金额最大
    1. 最右子结构 前i间房最大总金额
    2. 选择第i间房后，选择之后的房的金额不会影响前面的总金额
    改进点：
    dp[i] = max(dp[i-1],dp[i-2]+nums[i])
    使用滚动数组
    """
    n = len(nums)
    if n == 0:
        return 
    elif n <=1:
        return nums[0]
    # 使用dp
    # 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-1],dp[i-2]+nums[i])
    # return dp[n-1]
    """使用滚动数组"""
    pre = nums[0]
    cur = max(pre,nums[1])
    for i in range(2,n):
        cur,pre = max(pre+nums[i],cur),cur
    return cur

复杂度分析

令 n 为数组长度。

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

fhuang5 commented 2 years ago

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

        if (n == 0){
            return 0;
        }

        if (n == 1){
            return nums[0];
        }
        else{
            prev = nums[0];
            cur = Math.max(prev, nums[1]);
            for (int i = 2; i< n; i++){
                int temp = cur;
                cur = Math.max(prev + nums[i], cur);
                prev = temp;
            }
        }
        return cur;  
    }
}

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

xil324 commented 2 years ago

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [0] * len(nums); 
        if not nums:
            return 0;
        if len(nums) == 1:
            return nums[0];
        if len(nums) == 2:
            return max(nums[0], nums[1]); 
        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[len(nums)-1];

#time complexity: O(n) where n is the length of nums

maggiexie00 commented 2 years ago

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

currybeefer commented 2 years ago

做过

    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++)
        {
            dp[i]=max(dp[i-1],
                     dp[i-2]+nums[i-1]);
        }
        return dp[n];
    }
    int max(int a,int b)
    {
        return a>b? a:b;
    }

yinhaoti commented 2 years ago

class Solution:
    def rob(self, nums: List[int]) -> int:
        """
        dynamic programming
            dp[0], dp[1] = 0, 0
            dp[i] = max(dp[i-2] + nums[i - 2], dp[i-1])
        TC: O(n)
        SC: O(n)

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

    def rob(self, nums: List[int]) -> int:
        """
        Improve:
            TC: O(1)
        """
        if not nums: return 0
        if len(nums) == 1: return nums[0]

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

        return cur

L-SUI commented 2 years ago


/**
 * @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];
};

carterrr commented 2 years ago

package redo;

public class 打家劫舍_198 {

class Solution { public int rob(int[] nums) { if(nums.length == 1) return nums[0]; int[] dp = new int[nums.length]; // 前i 家能偷到的最大值 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 - 1], dp[i - 2] + nums[i]); // 前一家的最大值或者前前一家的最大值加上自己 System.out.println(dp[i]); }

  return dp[nums.length - 1];
}  //  100  2 9 54  这种其实最大值 154  dp[1] = dp[0] = 100 dp[2] = 109 dp[3] = 154  因为dp[1] 不是 2 而是 100

}

zhishinaigai commented 2 years ago

思路

动态规划+节省空间

代码

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

Shuchunyu commented 2 years ago

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] = nums[1];
    if (n > 2) {
        dp[2] = dp[0] + nums[2];
    }

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

}

freedom0123 commented 2 years ago

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

LQyt2012 commented 2 years ago

思路

动态规划，定义dp[i]为盗窃到第i间时的最大金额，i的下标从1开始。dp[i]=max(dp[i-1], (dp[i-2])+nums[i-1])。nums[i-1]表示第i间房的金额。

代码

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

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

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

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N), 优化后O(1)

JasonHe-WQ commented 2 years ago

思路：动态规划，每一间房子的金额只与前面两间房子相关代码：


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]

okbug commented 2 years ago

var rob = function(nums) {
    const n = nums.length;
    let f = [0], g = [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]);
};

Orangejuz commented 2 years ago

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

xiayuhui231 commented 2 years ago

题目

打家劫舍 https://leetcode.cn/problems/house-robber/

思路

DP

代码

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

}; ···

mo660 commented 2 years ago

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

tensorstart commented 2 years ago

思路

dp

代码

/**

@param {number[]} nums
@return {number} */ var rob = function(nums) { let dp = new Array(nums.length); if(nums.length===2){ nums.sort((a,b)=>{return a-b;}); return nums[nums.length-1]; } dp[0]=nums[0]; dp[1]=Math.max(nums[1],nums[0]); for(let i=2;i<nums.length;i++){ dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);

} console.log(dp) return dp[nums.length-1]; };

revisegoal commented 2 years ago

dp

定义状态：dp[i] = 前 i 间房子能够偷窃到的最高金额

状态转移：考虑算不算上第 i 间房子，算则因为不能和上一间相连，所以到前 i 间房子能获得的最高金额是上上间能获得的最高金额加上该间金额，否则是上间能获得的最高金额，dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

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 - 1], dp[i - 2] + nums[i]);
    }
    return dp[n - 1];
}
}

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

只需要dp[i - 1]和dp[i - 2]的信息，可优化至常数空间

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

xingchen77 commented 2 years ago

思路

DP问题

代码

    def rob(self, nums: List[int]) -> int:
        memo = [-1] * (len(nums) + 1)
        memo[-1] = 0
        return self.helper(0, nums, memo)

    def helper(self, n, nums, memo):
        if n >= len(nums):
            return 0
        if memo[n] != -1:
            return memo[n]
        memo[n] = max(self.helper(n + 1, nums, memo), self.helper(n+2, nums, memo) + nums[n])
        return memo[n]

复杂度

时间 O(n) \ 空间 O(1)

XXjo commented 2 years ago

思路

dp

代码

var rob = function(nums) {
    let n = nums.length;
    let dp = new Array(n).fill(0);   //表示前i间房能偷盗的最高金额
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for(let i = 2; i <= n; i++){
        dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
    }
    return dp[n - 1];
};

复杂度分析

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

miss1 commented 2 years ago

思路

f(n) = Math.max(f(n - 2) + nums[n], f(n - 1))

代码

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

复杂度

time: O(n)
space: O(1)

ha0cheng commented 2 years ago

思路：动态规划假设dp(k)为偷前k个房子所得到的最大收益，那么有 dp(k) = max(dp(k-1),dp(k-2)+nums[k]). 即第k个状态包括是否偷第k个房子，如果偷，则是dp(k-2)+nums[k]，如果不偷则是dp(k-1). 然后初始状态，如果有一个房子则偷，有两个则偷大的那个。

复杂度分析：时间复杂度：O(n), 每个状态只需求一次空间复杂度：O(n)，需要存储动态规划的状态

代码如下：

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

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

        return dp[len(nums) - 1]

sallyrubyjade commented 2 years ago

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  if (nums == null || !nums.length) {
    return 0;
  }
  let memo = new Array(nums.length).fill(-1);

  const dp = (nums, start) => {
    if (start >= nums.length) {
      return 0;
    }
    if (memo[start] != -1) {
      return memo[start];
    }
    let res = Math.max(
      dp(nums, start + 1),
      nums[start] + dp(nums, start + 2)
    );
    memo[start] = res;
    return res;
  };
  return dp(nums, 0);
};

linjunhe commented 2 years ago

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

        dp = [0 for _ in range(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]

flyzenr commented 2 years ago

def rob(self, nums: List[int]) -> int:
    prev = 0
    curr = 0

    # 每次循环，计算“偷到当前房子为止的最大金额”
    for i in nums:
        # 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
        # dp[k] = max{ dp[k-1], dp[k-2] + i }
        prev, curr = curr, max(curr, prev + i)
        # 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]

    return curr

taojin1992 commented 2 years ago

class Solution {
    // time: O(n), n = nums.length
    // space: O(n), can be optimized to be O(1)
    public int rob1(int[] nums) {
        // edge case
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];// by index i, max 
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            // dp[i-1], dp[i-2]
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.length - 1];
    }

    public int rob(int[] nums) {
        // edge case
        if (nums.length == 1) {
            return nums[0];
        }
        // by index i, max 
        int prev2 = nums[0];
        int prev1 = Math.max(nums[0], nums[1]);
        int cur = Math.max(prev1, prev2); // this line careful, cannot be 0 here, [1,1]
        for (int i = 2; i < nums.length; i++) {
            // dp[i-1], dp[i-2]
            cur = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;

        }
        return cur;
    }

}

houyanlu commented 2 years ago



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

        if (nums.size() == 1) {
            return nums[0];
        }

        int size = nums.size();
        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];

    }
};

~~~cpp

Jongeehsu commented 2 years ago

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

        dp[0] = nums[0];

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

        for(int i=1; i<n; i++) {
           if (i < 2) {
                // 从i=0 or 1 开始起步
                dp[i] = Math.max(dp[i-1], 0+nums[i]);
                // continue;
           } else {
                // 每个房间面临被偷和不被偷的可能，寻找最大值
                dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
           }
        }
        return dp[n-1];
    }
}

xixiao51 commented 2 years ago

Idea

Dynamic programing

Code

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

Complexity

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

gitbingsun commented 2 years ago

/ dp[i] given i houses, the max number the robberr can get max of -- rob i then dp[i-2]+nums[i] -- not rob i then dp[i-1] / class Solution { public: int rob(vector& nums) { int n = nums.size(); vector dp(n,0); dp[0] = nums[0]; if (n<=1) return dp[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];
}

};

Yongxi-Zhou commented 2 years ago

思路

dp

代码

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

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

复杂度

time O(N) space O(N)

leetcode-pp / 91alg-7-daily-check

【Day 55 】2022-05-25 - 198. 打家劫舍 #60

198. 打家劫舍

入选理由

题目地址

前置知识

题目描述

Idea

Code

Complexity

DP_bottomToTop

DP_topToBottom

C++

Solution 1

Solution 2

Solution 3

思路

代码

复杂度分析

时间复杂度

空间复杂度

思路

代码

复杂度分析

5.25

javascript #动态规划

思路

代码

复杂度分析

Code

思路

代码

复杂度

思路

代码

复杂度分析

思路

代码

复杂度分析

Idea

Code

Complexity:

Day55 思路

复杂度分析

动态规划

代码

复杂度

优化

复杂度

思路

关键点

代码

思路

代码

思路

代码

复杂度分析

题目

思路

代码

思路

代码

dp

思路

代码

复杂度

思路

代码

复杂度分析

思路

代码

复杂度

Idea

Code

思路

代码

复杂度