力扣213——打家劫舍 II

• 2020 年 2 月 19 日
• 筆記

这一篇是上一篇的扩展，需要针对特殊情况特殊考虑，当然其本质还是动态规划。

原题

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]  输出: 3  解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。  

示例 2:

输入: [1,2,3,1]  输出: 4  解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。       偷窃到的最高金额 = 1 + 3 = 4 。  

原题url：https://leetcode-cn.com/problems/house-robber-ii/

解题

这道题的变化是，同样是一个数组，但是首尾相连了，也就是成了一个环，那么原本递推的方式也就行不通了，因为任何一个节点其实地位都相等了，也就找不到最初的状态，无法进行递推了。

但我们可以将现在的问题转化成我们已经解决的问题，仔细想想。所谓的首尾相连，针对状态进行划分，可以有三种情况：

1. 首尾节点都不选择
2. 只选择首节点，不选择尾结点
3. 只选择尾结点，不选择首节点

因为我们最终是要求出最大值，那么只需要考虑后面两种情况，而这样的话，又可以转化成了原本的线性数组了。

接下来让我们看看代码：

class Solution {      public int rob(int[] nums) {          if (nums.length == 0) {              return 0;          }            if (nums.length == 1) {              return nums[0];          }            // 因为收尾相连，无法按照最初的动态规划来做，因为没有一个可以开始的点。          // 那么就将未知问题转化为已知问题，针对首尾两个节点，可以有三种情况：          // 1、首尾节点都不选择          // 2、只选择首节点，不选择尾结点          // 3、只选择尾结点，不选择首节点          // 因为是要取最大值，且是非负整数数据，所以只考虑后两种情况            return Math.max(              // 只选择首节点，不选择尾结点              calMax(nums, 0, nums.length - 2),              // 只选择尾结点，不选择首节点              calMax(nums, 1, nums.length - 1)          );      }        public int calMax(int[] nums, int start, int end) {          // 存储当前位置，下一个位置，和再下一个位置的结果          int current = 0;          int next_1 = 0;          int next_2 = 0;          // 动态规划，利用中间结果，寻找最大值          for (int i = end; i >= start; i--) {              current = Math.max(                  // 当前不偷                  next_1,                  // 当前偷                  nums[i] + next_2              );              next_2 = next_1;              next_1 = current;          }          return current;      }  }  

提交OK。

总结

以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要还是利用动态规划，只是需要大家进行思路转化，将未知转化为 已知，从而解决问题。