#
# @lc app=leetcode.cn id=198 lang=python3
#
# [198] 打家劫舍
#
# https://leetcode-cn.com/problems/house-robber/description/
#
# algorithms
# Easy (43.81%)
# Likes:    706
# Dislikes: 0
# Total Accepted:    94.3K
# Total Submissions: 213.8K
# Testcase Example:  '[1,2,3,1]'
#
# 
# 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
# 
# 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
# 
# 示例 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 。
# 
# 
#

# @lc code=start
class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp 状态:对于当前房间,想获得最大值,要不然是偷当前房间,要不然是上次偷比这次偷更有意义
        if not nums:
            return 0
        if len(nums)<=2:
            return max(nums)
        dp1 = nums[0]
        dp2 = max(nums[1],nums[0])
        for i in range(2,len(nums)):
            dp1,dp2 = dp2,max(dp1+nums[i],dp2)
        return dp2
# @lc code=end


ecd32d2cb5baca8bb2ab6e8673bf904ccf86325c
<mask token>

class Solution:
    <mask token>

class Solution:

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

#
# @lc app=leetcode.cn id=198 lang=python3
#
# [198] 打家劫舍
#
# https://leetcode-cn.com/problems/house-robber/description/
#
# algorithms
# Easy (43.81%)
# Likes:    706
# Dislikes: 0
# Total Accepted:    94.3K
# Total Submissions: 213.8K
# Testcase Example:  '[1,2,3,1]'
#
# 
# 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
# 
# 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
# 
# 示例 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 。
# 
# 
#

# @lc code=start
class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp 状态:对于当前房间,想获得最大值,要不然是偷当前房间,要不然是上次偷比这次偷更有意义
        if not nums:
            return 0
        if len(nums)<=2:
            return max(nums)
        dp1 = nums[0]
        dp2 = max(nums[1],nums[0])
        for i in range(2,len(nums)):
            dp1,dp2 = dp2,max(dp1+nums[i],dp2)
        return dp2
# @lc code=end

