#yyds干货盘点# LeetCode程序员面试金典：打家劫舍

1.简述：

你是一个计划沿街偷房子的专业小偷。每个房间都有一定的现金。影响你盗窃的唯一限制因素是相邻的房子配备了相互连接的防盗系统。如果两个相邻的房子在同一晚上被小偷闯入，系统会自动报警。

给出一个代表每栋房子存放金额的非负整数组，计算你 不触动报警装置的情况下 ，能在一夜之间偷到的最高金额。

示例 1：

输入：[1，2，3，1]

输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。

盗窃的最高金额 = 1 + 3 = 4 。

示例 2：

[2，7，9，3，1]

输出：12

解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 然后偷窃 5 号房屋 (金额 = 1)。

盗窃的最高金额 = 2 + 9 + 1 = 12 。

2.实现代码：

class Solution {    public int rob(int[] nums) {        if (nums == null || nums.length == 0) {            return 0;        }        int length = nums.length;        if (length == 1) {            return nums[0];        }        int[] dp = new int[length];        dp[0] = nums[0];        dp[1] = Math.max(nums[0], nums[1]);        for (int i = 2; i < length; i++) {            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);        }        return dp[length - 1];    }}