这是悦乐书的第187次更新，第189篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第46题（顺位题号是198）。你是一个专业的强盗，计划在街上抢劫房屋。 每个房子都藏着一定数量的钱，阻止你抢劫他们的唯一限制因素是相邻的房屋有连接的安全系统，如果两个相邻的房子在同一个晚上被闯入，它将自动联系警方。给出一个代表每个房子的金额的非负整数列表，确定今晚可以抢劫的最大金额而不警告警察。例如：
输入：[1,2,3,1]
输出：4
说明：Rob house 1（money = 1）然后抢房子3（钱= 3）。您可以抢夺的总金额= 1 + 3 = 4。
输入：[2,7,9,3,1]
输出：12
说明：Rob house 1（money = 2），rob house 3（money = 9）和rob house 5（money = 1）。您可以抢夺的总金额= 2 + 9 + 1 = 12。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
初始思路是偶数、奇数下标的元素分别求和，然后判断其中的最大值，但是有个问题，此思路只考虑了隔一个元素，那要是隔两个、三个甚至更多呢？在每次算完奇数或者偶数下标元素之和之后，还要和已有的偶数下标元素和或者奇数下标元素和做最大值判断，最后再取偶数下标元素和、奇数下标元素和中的最大值。
特殊情况：当数组为null或者数组中没有任何元素时，直接返回0。
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int sum = 0;
int sum2 = 0;
for(int i=0; i<nums.length; i++){
if (i%2 == 0) {
sum = Math.max(sum+nums[i], sum2);
} else {
sum2 = Math.max(sum2+nums[i], sum);
}
}
return Math.max(sum, sum2);
}此解法的时间复杂度是O(n)，空间复杂度是O(1)。
03 第二种解法
使用动态规划算法。
第一步，我们找到此问题的递归关系，强盗有两种选择：
a）抢劫当前的房子i
b）不抢劫当前的房子i
如果选择选项“a”，则意味着无法抢夺之前的i-1房屋，但可以安全地前往前一个i-2之前的房屋并获得随后的所有累积战利品。
如果选择了一个选项“b”，强盗将从抢劫i-1和剩下所有建筑物中获得所有可能的战利品。
因此，利益最大的结果就有两种可能：
1）抢劫当前房屋 + 前一次房屋抢劫
2）从之前的房屋抢劫和之前捕获的任何战利品中掠夺
对此，可以得出以下公式：
rob(i) = Math.max( rob(i-2) + currentHouseValue, rob(i-1) )第二步，在分析出了递归关系后，我们可以得到自顶向下的递归解法，对此，我们可以写出第一版的代码：
public int rob(int[] nums) {
return rob(nums, nums.length-1);
}
private int rob(int[] nums, int i) {
if (i < 0) {
return 0;
}
return Math.max(rob(nums, i-2) + nums[i], rob(nums, i-1));
}第三步，上面的递归算法，会造成大量的重复计算，对此可以使用备忘录算法来记录前一步的值，同样是使用自顶向下的递归算法。
public int rob(int[] nums) {
int[] memo = new int[nums.length + 1];
Arrays.fill(memo, -1);
return rob(nums, nums.length - 1);
}
private int rob(int[] nums, int i) {
if (i < 0) {
return 0;
}
if (memo[i] >= 0) {
return memo[i];
}
int result = Math.max(rob(nums, i-2) + nums[i], rob(nums, i-1));
memo[i] = result;
return result;
}Arrays.fill(memo, -1)方法表示memo数组的元素全部由-1来填充。
第四步，备忘录算法不变，可以将递归算法用迭代替代，变成自底向上的方式。
public int rob(int[] nums) {
if (nums.length == 0) return 0;
int[] memo = new int[nums.length + 1];
memo[0] = 0;
memo[1] = nums[0];
for (int i = 1; i < nums.length; i++) {
int val = nums[i];
memo[i+1] = Math.max(memo[i], memo[i-1] + val);
}
return memo[nums.length];
}第五步，可以注意到，在上一步中我们只使用memo[i]和memo[i-1]，所以只需要两步。我们可以将它们保存在2个变量中，而不必使用备忘录算法。
public int rob(int[] nums) {
if (nums.length == 0) return 0;
int prev1 = 0;
int prev2 = 0;
for (int num : nums) {
int tmp = prev1;
prev1 = Math.max(prev2 + num, prev1);
prev2 = tmp;
}
return prev1;
}上述解法的思路参考至@heroes3001的说明，写的很好，就按照自己的理解翻译了下，按照这五个步骤基本可以解决类似的动态规划算法问题。最下方的原文链接就是该作者原答案。
04 小结
算法专题目前已连续日更超过一个月，算法题文章46+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
- 还没有人评论，欢迎说说您的想法！
客服
