Problem

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.

问题描述

给定一个数组 nums，从 nums 中选出一些不相邻的元素，求这些元素和的最大值。

备注

• nums 数组中的所有元素都大于等于 0

样例

输入: [1, 2, 3, 1]
输出: 4
解释: 选择 1、3 并求和，得到 4。

解法 1

设 f 和 g 是两个数组，f[i-1] 表示从 nums 的前 i 个元素中选择 nums[i-1] 及不相邻的元素时这些元素和的最大值，g[i-1] 表示从 nums 的前 i 个元素中不选择 nums[i-1] 及不相邻的元素时这些元素和的最大值。则考虑 nums 的前 i+1 个元素中选择不相邻的元素和的最大值

• 若选择 nums[i]，则 f[i]=nums[i]+g[i-1]
• 若不选择 nums[i]，则 g[i]=max(f[i-1], g[i-1])

最后返回 f[n-1] 和 g[n-1] 的最大值即可。

参考代码:

class Solution:
    def rob(self, nums):
        if not nums:
            return 0
        n = len(nums)
        f = [0] * n
        g = [0] * n
        f[0] = nums[0]
        for i in range(1, n):
            f[i] = nums[i] + g[i-1]
            g[i] = f[i-1] if f[i-1] > g[i-1] else g[i-1]
        return f[-1] if f[-1] > g[-1] else g[-1]