LeetCode

Appearance

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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

Example 1:

Input: nums = [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: nums = [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.

 

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400
Related Topics
  • 数组
  • 动态规划

  • 👍 3289
  • 👎 0

    • 思路 ​

    定义 dp[i] 为当前房子的最大收益 则 dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])

    解法一 ​

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


        dp = [0] * 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]

    复杂度分析 ​

    • 时间复杂度 O(N)
    • 空间复杂度 O(N)

    解法二 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        elif len(nums) == 1:
            return nums[0]
        pre2 = nums[0]
        pre1= max(nums[0], nums[1])
        cur = pre1
        for i in range(2, len(nums)):
            cur= max(pre1, pre2 + nums[i])
            pre2 = pre1
            pre1 = cur

        return cur


        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(N)
    • 空间复杂度 O(1)