[LeetCode]动态规划之打家劫舍ⅠⅡⅢ

在文章[LeetCode]动态规划及LeetCode题解分析中，Jungle介绍到求解动态规划类问题，一般分为三个步骤：

1. 明确数组元素代表的含义
2. 寻找递推关系，务必考虑特殊情况下的递推关系
3. 数组初始化

当然，很多文章里把数组每个元素叫做一种“状态”，把相邻数组元素之间的递推关系叫做“状态转移方程”，数组初始化叫做“初始状态”。

文章动态规划LeetCode[简单]题全解利用上面文章的解题步骤完成了LeetCode上面难度为“简单”的题目。本文Jungle将继续运用上述步骤，完成打家劫舍系列题目。

LeetCode上打家劫舍系列一共三道题目，其中一道简单题，两道中等题：

1

198.打家劫舍

https://leetcode-cn.com/problems/house-robber/

这道题在之前的文章里动态规划LeetCode[简单]题全解已经解过，这里再简单说下：

一个小偷，计划偷窃沿街的房屋。每间房内藏有一定的现金，影响你偷窃的唯一制约因素是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 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 。

（1）明确数组含义

dp[i]——到第i号房屋为止，偷窃到的最高金额。

（2）寻找递推关系

到达第i号房屋时，如果第i-1已经偷盗了，显然第i号房屋不能再行窃；如果第i-1号房屋没有被偷盗，则比较偷盗第i号房屋后的最高金额与截止第i-1号房屋为止的最高金额dp[i-1]的大小：

dp[i] = max(dp[i-1], dp[i-2]+nums[i])

（3）数组初始化

dp[0] = nums[0]

dp[1] = max(nums[0],nums[1])

（4）Code

int rob(vector<int>& nums) {
  int len = nums.size();
  if (len == 0){
    return 0;
  }
  if (len == 1){
    return nums[0];
  }
  if (len == 2){
    return nums[0]>nums[1] ? nums[0] : nums[1];
  }
  int *dp = new int[nums.size()];
  dp[0] = nums[0];
  dp[1] = nums[1]>nums[0] ? nums[1] : nums[0];
  for (int i = 2; i<nums.size(); i++){
    dp[i] = dp[i - 2] + nums[i]>dp[i - 1] ? dp[i - 2] + nums[i] : dp[i - 1];
  }
  return dp[nums.size() - 1];
}

2

213.打家劫舍Ⅱ

https://leetcode-cn.com/problems/house-robber-ii/

你是一个专业的小偷，偷窃沿街的房屋，每间房都藏有现金。这个地方所有房屋围成一圈，这意味着第一个房屋和最后一个房屋紧挨着。相邻的房屋装有相互连通的防盗系统，如果两间相邻房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 示例 1: 输入: [2,3,2] 输出: 3 解释: 你不能先偷窃1号房屋(2)，然后偷窃3号房屋(2), 因为他们是相邻的。 示例 2: 输入: [1,2,3,1] 输出: 4 解释: 你可以先偷窃1号房屋(1)，然后偷窃3号房屋(3)。偷窃到的最高金额=1+3=4 。

这题与第一题的区别在于房屋是一个圈，首尾相连，在偷窃第一家和最后一家时，需要额外考虑。

（1）明确数组含义

与之前一致，dp[i]——到第i号房屋为止，偷窃到的最高金额。

（2）寻找递推关系

同样，递推关系与之前一致：dp[i] = max(dp[i-1], dp[i-2]+nums[i])

那么怎么考虑首尾相连的问题呢？假设一共有n户人家，

• a. 假设小偷偷了第一家，那么他肯定不能偷窃最后一家，至多偷盗第n-1家
• b. 假设小偷没有偷第一家，他就可以偷盗最后一家

那不妨我们使用两个数组来计算上述两种情况，最后比较两种情况的最大值即可。

（3）数组初始化

• 情况a：dp[0] = nums[0], dp[1] = dp[0]（因为这种情况情况小偷确定偷了第一家，所以不能偷第二家）
• 情况b：dp[0] = 0, dp[1] = dp[1]（因为这种情况情况小偷确定没偷第一家）

（4）Code

int max(int a, int b)
{
    return a>b ? a : b;
}

int rob(vector<int>& nums) 
{
    int len = nums.size();
    if (len == 0){
      return 0;
    }
    if (len == 1){
        return nums[0];
    }

    int *dp = new int[len];
    int *dp2 = new int[len];
    dp[0] = nums[0];
    dp[1] = nums[0];
    dp2[0] = 0;
    dp2[1] = nums[1];

    for (int i = 2; i<len; i++){
      dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
      dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i]);
    }
    return max(dp[len - 2], dp2[len - 1]);
}

3

337.打家劫舍Ⅲ

https://leetcode-cn.com/problems/house-robber-iii/

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

解法1

通过前面两次偷盗，我们都知道递推关系是

dp[i] = max(dp[i-1], dp[i-2]+nums[i])

然而这一题的区别是引入了二叉树。二叉树不太适合用数组来保存历史状态。但同样可以使用动态规划来求解。那不妨我们分析一下以下一个完全二叉树的情况：

根据题目要求，有以下两种偷盗情况：

• 1+4+5+6+7：即根节点，根节点的左子树的左右子树，和根节点的右子树的左右子树
• 2+3：即根节点的左右子树

为什么不考虑2+6+7和3+4+5呢？假设以2为根节点，那dp[2]有可能等于4+5，同理，dp[3]也可能等于6+7，而这种情况已经被上面第一种情况包含了，所以可以不必考虑。

所以根据上述情况，可以得到递推关系为：

dp[node] = max（dp[l]+dp[r],

node->val+dp[ll]+dp[lr]+dp[rl]+dp[rr]）

代码如下：

int rob(TreeNode* root) {
    if (root == NULL){
      return 0;
    }
    int res = 0;
    res += root->val;
    if (root->left != NULL){
      res += (rob(root->left->left) + rob(root->left->right));
    }
    if (root->right != NULL){
      res += (rob(root->right->left) + rob(root->right->right));
    }
    return max(res, rob(root->left) + rob(root->right));
}

但是上述代码会超出时间限制，因此需要考虑一种更优化的办法。

解法2

试想一二叉树，如上图，如果偷了2，就不能偷4和5，如果没偷盗2，就可以偷盗4和5。也就是说，每个节点有两种可能的状态，在不同状态下由不同的偷盗金额。那么我们可以使用一个含有两个元素的一维数组来保存每个节点的两种状态：

• cur[0]：该号房屋没有被偷盗，与该号房屋相邻的房屋可以被偷盗，此种状态下的偷盗金额；
• cur[1]：该号房屋被偷盗，与该号房屋相邻的房屋不能被偷盗，此种状态下的偷盗金额；

最后比较cur[0]和cur[1]，取较大值。

采用后序遍历，最后访问根节点。所以，递推关系为：

• cur[0] = max(left[0], left[1])+max(right[0], right[1])
• cur[1] = curNode->val+left[0]+right[0]

代码如下：

int* postOrder(TreeNode *node){
    int *cur = new int[2];
    cur[0] = 0;
    cur[1] = 0;
    if (node == NULL){
      return cur;
    }
    int* left = postOrder(node->left);
    int* right = postOrder(node->right);

    cur[0] = max(left[0], left[1]) + max(right[1], right[0]);
    cur[1] = node->val + left[0] + right[0];
    return cur;
}
int rob(TreeNode* root) {
    if (root == NULL){
      return 0;
    }
    int *res = postOrder(root);
    return max(res[0], res[1]);
}