【LeetCode-动态规划】打家劫舍 III

题目描述

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

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

题目链接: https://leetcode-cn.com/problems/house-robber-iii/

思路1

因为不能打劫两个直接相连的房子,所以对于一个3层的树来说,有两种打劫的方法:

  • 打劫爷爷节点+打劫孙子节点:root->val+rub(root->left->left)+rub(root->left->right)+rub(root->right->left)+rub(root->right->right);
  • 打劫父亲节点:rub(root->left)+rub(root->right);

取两种方法的最大值即可。这种方法可以使用递归实现,代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        if(root==nullptr) return 0;

        int money = root->val;
        if(root->left!=nullptr){
            money += (rob(root->left->left) + rob(root->left->right));
        }
        if(root->right!=nullptr){
            money += (rob(root->right->left) + rob(root->right->right));
        }

        return max(money, rob(root->left)+rob(root->right));
    }
};
  • 时间复杂度:O(2^N)
  • 空间复杂度:O(h)

该方法由于时间复杂度过高未通过。

思路2

思路1时间复杂度过高的原因是有很多节点被重复计算了。为了避免重复计算,我们可以使用哈希表记录下来从某节点开始能抢劫到的最大钱数,这样在递归的过程中,如果节点在哈希表中出现,则直接返回对应的值,也就是备忘录算法。代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        if(root==nullptr) return 0;
        unordered_map<TreeNode*, int> dict;
        return doRob(root, dict);
    }

    int doRob(TreeNode* root, unordered_map<TreeNode*, int>& dict){
        if(root==nullptr) return 0;
        if(dict.find(root)!=dict.end()) return dict[root];

        int money = root->val;
        if(root->left!=nullptr){
            money += (doRob(root->left->left, dict) + doRob(root->left->right, dict));
        }
        if(root->right!=nullptr){
            money += (doRob(root->right->left, dict) + doRob(root->right->right, dict));
        }
        
        int result = max(money, doRob(root->left, dict)+doRob(root->right, dict));
        dict[root] = result;    // 注意位置
        return result;
    }
};

思路3

使用动态规划。对于每个节点都有两种选择:抢劫和不抢劫,使用1表示抢劫,使用0表示不抢劫,我们使用一个二维数组int res[2]来表示,则

  • 抢劫该节点:rob(root)[1] = root->val+rob(root->left)[0]+rob(root->right)[0];
  • 不抢劫该节点:rob(root)[0] = max(rob(root->left)[0],rob(root->left)[1]) + max(rob(root->right)[0],rob(root->right)[1]);

代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        if(root==nullptr) return 0;
        int* money = doRob(root);
        return max(money[0], money[1]);
    }

    int* doRob(TreeNode* root){
        if(root==nullptr){
            int* t = new int[2];
            memset(t, 0, sizeof(t));
            return t;
        };
        
        int* result = new int[2];
        memset(result, 0, sizeof(result));
        int* left = doRob(root->left);
        int* right = doRob(root->right);
        result[0] = max(left[0], left[1]) + max(right[0], right[1]);
        result[1] = root->val + left[0] + right[0];
        return result;
    }
};

参考

1、https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/

上一篇:团灭 LeetCode 打家劫舍问题


下一篇:letcode动态规划专题讲解