[LeetCode] 198. House Robber 打家劫舍

2021年09月15日 阅读数:2
这篇文章主要向大家介绍[LeetCode] 198. House Robber 打家劫舍,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.html

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.java

Example 1:python

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:数组

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

假设你是一位专业的盗贼计划打劫沿一条街的房子,每一个房子藏着必定数额的钱,你不能同时打劫相邻的两个房子,由于会报警,求一夜能打劫到的最多钱。post

解法:动态规划DP。本质至关于在一列数组中取出一个或多个不相邻数,使其和最大。url

State: dp[i],表示到第i个房子时可以抢到的最大金额。htm

Function: dp[i] = max(num[i] + dp[i - 2], dp[i - 1])blog

Initialize: dp[0] = num[0], dp[1] = max(num[0], num[1]) 或者 dp[0] = 0, dp[1] = 0get

Return: dp[n]it

Java:

public class Solution {
    public int rob(int[] nums) {
        if(nums.length <= 1){
            return nums.length == 0 ? 0 : nums[0];
        }
        // a是上次的最大收益
        int a = nums[0];
        // b是当前的最大受益
        int b = Math.max(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++){
            int tmp = b;
            // 当前的最大收益是两种选择里较大的那个
            b = Math.max(a + nums[i], b);
            a = tmp;
        }
        return b;
    }
}

Java:

class Solution {
    public int rob(int[] nums) {  
        int curMax = 0, curPrePreMax = 0;  
        for (int cur : nums) {  
            int temp = curMax;  
            curMax = Math.max(curMax, curPrePreMax + cur);  
            curPrePreMax = temp;  
        }  
        return curMax;  
    }
} 

Python:

class Solution:
    # @param num, a list of integer
    # @return an integer
    def rob(self, num):
        if len(num) == 0:
            return 0
            
        if len(num) == 1:
            return num[0]
        
        num_i, num_i_1 = max(num[1], num[0]), num[0]
        for i in xrange(2, len(num)):
            num_i_1, num_i_2 = num_i, num_i_1
            num_i = max(num[i] + num_i_2, num_i_1);
        
        return num_i

Python:

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        vis = set()
        for num in nums:
            if num in vis: return True
            vis.add(num)
        return False  

Python:

class Solution:
    def rob2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        last, now = 0, 0
        for i in nums:
            last, now = now, max(last + i, now)
        return now

Python: wo

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
    
        pre_pre = nums[0]
        pre = max(nums[0], nums[1])
        for i in xrange(2, len(nums)):
            cur = max(pre, pre_pre + nums[i])
            pre_pre, pre = pre, cur
            
        return pre   

C++:

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

C++:

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

   

相似题目:

[LeetCode] 213. House Robber II 打家劫舍 II

  

All LeetCode Questions List 题目汇总