Daily LeetCode 198. House Robber

https://leetcode.com/problems/house-robber/

Easy

问题描述：

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.

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.

Example 1:

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.

思路及代码：

假设你是一个劫匪，给定一个list，内容是每一户的财产价值，相邻的房子之间有报警系统，因此只能选择一个洗劫一空，要求算出最大收入。

这是一题很简单的动态规划的问题，我们维护一个一维数组dp，dp[i]表示到第i户时的最大收益。在第i户，我们比较nums[i]+dp[i-2]和dp[i-1]大小，从而决定当前执行抢劫操作，还是跳过这一户。

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

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

        return max(dp)