:-: 9.3 打家劫舍 * * * * * **题干：** 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 示例 1: ~~~ 输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 ~~~ 示例 2: ~~~ 输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。 ~~~ **题目分析：** 这种简单的动态规划题目，首先要先思考怎么分析动态规划方程（其实对于新手来说这就是个找规律的过程），我们不是大神， 一眼就看出。我们可以从个例分析到通用，再到特例。 我们可以先分析没有元素的情况，没有元素则f(0) = 0； 然后分析元素为1的时候f(1) = nums[0]； 元素为2的时候，f(2) = Math.max(sums[0],sums[1])； 元素为3的时候，需要作比较，nums[0]和nums[2]相加与nums[1]做对比，也就是f(3) = Math.max(sums[0] + sums[2],sums[1])； 元素为4的时候，f(4) = Math.max(sums[1] + sums[3],sums[0] + sums[2])，看到这里应该就有一些规律了吧，但是这真的对吗？？？，哈哈哈，题上并没有说间隔两个的不可以，比如a = [2,1,1,2],这个时候a[0] + a[2]与a[1] + a[3] = 3 但是正确的答案应该为4呀，也就是a[0]+a[3] = 4,这个时候就应该回去看看我们的分析有错误没,原来我们在f(3)的时候就分析错误了,f(3) =Math.max(f(1)+nums[2],f(2)),看到这里可能该有一丝疑惑，为什么要这样呢（为什么第一个与第二个元素要做对比）？ 我们分析一下当数组为[2,1,1,2]的时候，假设只考虑间隔一个的正常情况下，（以下为下标）0与2结合，1与3结合没问题，但是1元素能结合的，我0元素也能结合，他不能结合的2元素我也可以结合，此时1元素还小于0元素，我何不直接替代你1元素，这样就相当于考虑了0元素可以和间隔一个和间隔两个结合的情况，可能有些绕，多多担待，能力有限。 此时会发现我们找的是当前房屋金额和之前的间隔房屋最大金额与相邻房屋最大金额的最大值,得出动态规划方程：f(n) = Math.max(nums[i]+f(n-2),f(n-1)); 我们还可以这样想，假设这个小偷已经偷了前面n个房子了（0 ~ n - 1），那么现在的问题就是怎么处理第n + 1个房子，无非就两种情况（偷还是不偷，这是个问题？），假设rob[n]是偷取了第n + 1个房子的金额，cost[n - 1]是没偷取第n + 1个房子的金额，我们由此可得出动态规划方程： rob[n] = nums[n] + cost[n - 1] cost[n] = Math.max(rob[n], cost[n - 1]) **新手有可能遇到的解题思路陷阱：** 只考虑了间隔一个的情况，没有考虑间隔两个也可以的情况 **解题思路分析以及代码实现：** 第一种思路：数组法 第一种思路代码： ~~~ public static int rob(int[] nums) { if (nums.length == 1) { return nums[0]; } if (nums.length == 2) { return Math.max(nums[0], nums[1]); } if (nums.length > 2) { int cost[] = new int[nums.length + 1]; cost[0] = nums[0]; cost[1] = Math.max(nums[0], nums[1]); for (int i = 2; i <= nums.length; ++i) { int sum = i == nums.length ? 0 : nums[i]; cost[i] = Math.max(cost[i - 2] + sum, cost[i - 1]); } return cost[nums.length]; } return 0; } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(n)。 第二种思路：迭代法 第二种思路代码： ~~~ public static int rob(int[] nums) { if (nums.length < 1 || nums == null) { return 0; } int length = nums.length; if (length == 1) { return nums[0]; } if (length == 2) { return Math.max(nums[0], nums[1]); } int sum = 0; int sum1 = nums[0]; int sum2 = Math.max(nums[0], nums[1]); int i = 2; while (i < length) { sum = Math.max(sum1 + nums[i], sum2); sum1 = sum2; sum2 = sum; i++; } return sum2; } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**