1. 题目描述
2. 题目分析
- 经典的DP问题，也是DP的入门。条件：小偷不能偷相邻的房间。
- 如果我们当前对于最后一户人家，我们决定偷他：
那我们获取的最大利益是：nums[i] + opt[i - 2]这里的opt代表，我们从第一家偷到第几家的收益
如果我们不偷的话，那我们获取的最大利益是：opt[i - 1]
我们可以列关系式：opt[i] = Math.max(opt[i-1], nums[i] + opt[i-2]); - 我们需要找到出口，这个题目的出口比较简单，也就是
opt[0] = nums[0]、opt[1] = Math.max(nums[0], nums[1]);
3. 题目代码
class Solution { public int rob(int[] nums) { int[] opt = new int[nums.length]; if (nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } opt[0] = nums[0]; opt[1] = Math.max(opt[0], nums[1]); for (int i = 2; i < nums.length; i++) { opt[i] = Math.max(opt[i - 1], nums[i] + opt[i - 2]); } return opt[nums.length - 1]; } }
