力扣热门100题之打家劫舍

核心思路

不能偷相邻的，所以：

• 到第i个房子时，有两种选择：
  1. 偷：那前一个不能偷，总钱 =dp[i-2] + nums[i]
  2. 不偷：总钱 =dp[i-1]

所以递推公式：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

完整代码实现：

class Solution { public int rob(int[] nums) { int n = nums.length; if(n == 0) return 0; if(n == 1) return nums[0]; int pre2 = 0; //dp[i - 2] int pre1 = nums[0]; //dp[i - 1] for(int i =1 ;i<n;i++){ int cur = Math.max(pre1,pre2 + nums[i]); // 偷 不偷 pre2 = pre1; pre1 = cur; } return pre1; } }