198. 打家劫舍

链接

https://leetcode.cn/problems/house-robber/description/

思路 

相邻的要么选，要么不选。

设置dp[i]表示以nums[i]为结尾的序列的最大收益。所以状态转移方程为：dp[i] = max(dp[i-1], dp[i-2]+nums[i]).

根据这个定义，我们来对前2个元素初始化就ok了。

代码

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