Q198 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 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.

解题思路:

此题的意思是,给定一个非负整数列表,从中选取元素,使得元素两两不相邻,找到满足条件的这些元素的最大和。

假设列表长度为 n,先观察规律:

当 n = 0 时,列表为空,返回 0
当 n = 1 时,列表只有一个元素,返回 nums[0]
当 n = 2 时,列表有两个元素,返回 max(nums[0], num[1])
当 n = 3 时,列表返回的下标组合可能为 [0,2] 和 [1]
当 n = 4 时,列表返回的下标组合可能为 [0,2] 、[1,3] 和 [0,3]
当 n = 5 时,列表返回的下标组合可能为 [0,2,4] 、[1,3] 、[0,3] 和 [1,4]
当 n = 6 时,列表返回的下标组合可能为 [0,2,4] 、 [1,3,5]、[0,3,5]、[1,4] 和 [0,2,5]
.....

以 n = 6 为例,[0,2,4] 和 [1,4] 均可以由 n = 5 时得到; [1,3,5]、[0,3,5] 和 [0,2,5] 可以由 n = 4 的每个元素加上 [5] 得到。

由此可以得到递归规律:

设 k 为列表最大下标,则有:
f(0) = nums[0]
f(1) = max(num[0], num[1])
f(k) = max(f(k-2) + nums[k], f(k-1))

因此,此题可以使用递归求解。时间复杂度 O(n),空间复杂度 O(1)。

Python实现:
class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        high = len(nums) - 1
        if high == -1:
            return 0
        elif high == 0:
            return nums[0]
        elif high == 1:
            return max(nums[0], nums[1])
        else:
            return max(self.rob(nums[:high-1]) + nums[high], self.rob(nums[:high]))

这种方法得到的答案是正确的,但是在提交的时候会超时。因此,需要改写为非递归的方法,如下:

class Solution(object):
    def rob2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # pre2 相当于 f(k-2), pre1 相当于 f(k-1), now 相当于 f(k)
        pre2 = pre1 = now = 0  
        for num in nums:
            pre2 = pre1
            pre1 = now
            now = max(pre2 + num, pre1)
        return now

a = [6,3,10,8,2,10,3,5,10,5,3]  
b = Solution()
print(b.rob2(a))  # 39  # 下标 [0, 2, 5, 8, 10] = 6 + 10 + 10 + 10 + 3 = 39

这种将递归方法改写为非递归方法与斐波那契数列改写方法类似,可以参考题目 Q70 Climbing Stairs

观察上述非递归方法,可以更近一步简化,即 pre2 = pre1; pre1 = now 可以合并为一句 pre2 = now, 这时 now = max(pre2 + num, pre1) 变为 now = max(pre2 + num, now):

class Solution(object):
    def rob3(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        last = now = 0 
        for num in nums:
            last, now = now, max(last + num, now)
        return now

a = [6,3,10,8,2,10,3,5,10,5,3]  
b = Solution()
print(b.rob3(a))  # 39  # 下标 [0, 2, 5, 8, 10] = 6 + 10 + 10 + 10 + 3 = 39

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏wym

18年暑假多校赛第一场 1004

题目地址http://acm.hdu.edu.cn/showproblem.php?pid=6301

8720
来自专栏书山有路勤为径

包含min函数的栈

LeetCode 155. Min Stack 设计一个栈,支持如下操作,这些操作的算法复杂度需要是常数级,O(1) 1.push(x) : 将元素x压入...

10910
来自专栏程序生活

最大连续子序列和

https://blog.csdn.net/bitcarmanlee/article/details/51526010

11620
来自专栏数据结构与算法

1341 与3和5无关的数

1341 与3和5无关的数 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description ...

28940
来自专栏Jack-Cui

第七天、判断三角形的类型

    根据输入的三角形的三条边判断三角形的类型,并输出它的面积和类型。 C代码: /*第七天、判断三角形的类型*/ #include <stdio.h> ...

22400
来自专栏python3

python random模块

随机输出一个0~4的数字和range()输出的数字,去比较。猜对了,就是字母,否则是数字

9020
来自专栏Jack-Cui

Day3、Python

题目 输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。 1、程序分析     根据题意可知,需要用到字符串的操作方法。本题中要用到的三...

18500
来自专栏人工智能LeadAI

Python中对字节流/二进制流的操作:struct模块简易使用教程

前言 前段时间使用Python解析IDX文件格式的MNIST数据集,需要对二进制文件进行读取操作,其中我使用的是struct模块。查了网上挺多教程都写的挺好的,...

56850
来自专栏用户2442861的专栏

NumPy简明教程(二、数组1)

http://blog.csdn.net/sunny2038/article/details/9002531

11010
来自专栏Jed的技术阶梯

图解冒泡排序

在上面实现的代码中,即使n个数本来就是有序的,也会进行(n-1)次排序(只比较,不交换) 优化:当数组已经有序后,就中断循环

21530

扫码关注云+社区

领取腾讯云代金券