本文主要是介绍leetcode198 打家劫舍，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路
有点像走楼梯，只是考虑相邻，也就是说你打算偷a[i],那你就不能偷a[i-1]的，然后可以递归的想。
如果money[i]表示第i个房间的钱，sum[i]表示此时在第i个房间一共偷到的最多的钱
错误公式
sum[i] = sum[i-1] + money[i]; 就是隔着偷
最后只需要计算最后两个就可以了
1 2 3 4 计算 (1+3 =4 )<( 2+4 =6)
但是也可以偷第1家（1）第4家（4）=5 啊，这个也是满足条件的
比如这个例子：
100 7 2 9 5 最大值是 100+9 =109
即 sum[i] = sum[i-2] +money[i];
那还会不会隔更多呢，不会的
比如 1 2 3 4 5 可以计算5 + 1， 但是5+1 一定不会是最大。因为你可以5+3+1,即 你在计算sum[3]的时候已经计算了1+3
正确公式
sum[i] = max(sum[i-1], sum[i-2])
代码
public int rob(int[] nums) {if (nums.length == 1){return nums[0];}if (nums.length == 2) {return Math.max(nums[0], nums[1]);}int[] a = new int[3];//为了节省空间a[0] = nums[0];a[1] = nums[1];a[2] = nums[2]+nums[0];int cnt = 0;for (int i = 3; i< nums.length;i++){cnt = Math.max(a[0],a[1])+ nums[i];a[0] = a[1];a[1] = a[2];a[2] = cnt; }return Math.max(a[1],a[2]);
}
这篇关于leetcode198 打家劫舍的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
