P71. 抢劫连排房子

leetcode 198 lintcode 392 动态规划 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,有一个强盗要去抢一排连排房子,每个房子里放着正整数金额的钱,可以用一个整数数组来表示。这个强盗唯一的限制就是不能同时抢相邻的两个房子,那么请问,这个强盗最多可以抢到多少钱。

比如说,这排房子里放着的钱是整数数组 nums:

8, 1, 2, 9, 6

在不能抢相邻房子的情况下,最多可以抢到的钱是 17,就是抢 8 和 9 这两个数字对应的房子。

抢完 8 和 9 后,其它的房子就都不能抢了,因为都与这两所房子相邻。

而其它的抢劫组合也都没有 17 大,比如抢 8,2,6,这三个房子不相邻可以同时抢,但抢它们的话能抢到的钱只有 16,没有 17 大。

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。