[Vssue]0198.打家劫舍.md

[youngyangyang04]

https://www.programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html

[Du1in9]

if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];

dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];

// 例: nums = [2,7,9,3,1], dp = [2,7,0,0,0]
i = 2: dp[2] = max(7, 2+9) = 11 (偷), dp = [2,7,11,0,0]
i = 3: dp[3] = max(11, 7+3) = 11 (不偷), dp = [2,7,11,11,0]
i = 4: dp[4] = max(11, 11+1) = 12 (偷), dp = [2,7,11,11,12]