做网站还有流量么/宁波网站关键词优化公司

打家劫舍

题目：

这道题也是一个经典的DP问题，我们一般都是用倒退的思路：

假设第i间是最后一间，第i-1间就是偷不到的，只能偷第i-2间，那么对于第i间就有两种情况，偷或者不偷：

所以我们设置一个DP数组maxArr[]，DP方程就是：

maxArr[i]=Math.max(maxArr[i-2]+nums[i],maxArr[i-1]);

所以代码就很明显了;

class Solution {public int rob(int[] nums) {int total = nums.length;if(total==1){return nums[0];}int[] maxArr = new int[total];maxArr[0]=nums[0];maxArr[1]=Math.max(nums[0], nums[1]);//假设i是最后一间，i-1就是偷不到的，只能偷i-2，那么就有两种情况，偷或者不偷for (int i = 2; i <total ; i++) {maxArr[i]=Math.max(maxArr[i-2]+nums[i],maxArr[i-1]);}return maxArr[total-1];}
}