打家劫舍3-递归到动态规划

337. 打家劫舍

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
思路一：递归
1、偷该节点，则不偷左右节点，偷左右节点的左右节点。
int method1 = root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right)
2、不偷该节点，则偷该节点的左右节点。
int method2 = rob(root.left) + rob(root.right);
int result = Math.max(method1, method2);

class Solution {
public:
    int rob(TreeNode* root) { 
        if(!root)
            return 0;
        int s1=root->val;
        if(root->left)
        {
            s1+=rob(root->left->left)+rob(root->left->right);
        }
        if(root->right)
        {
            s1+=rob(root->right->left)+rob(root->right->right);
        }
        int s2=rob(root->left)+rob(root->right);
        return max(s1,s2);
    }
};

递归的时间复杂度O（2^n），空间复杂度O（n）。然而，递归超时了，怎么办呢？
思路二：动态规划
可以发现，在递归时，每求一次节点金额，需要重复访问多次左右子树，所以可以提前把偷过的子树盗取的最大金额保存到一个哈希表。从底向上保存偷或不偷该节点能达到的最大金额。
以上的算法对二叉树做了一次后序遍历，时间复杂度是 O(n)；由于递归会使用到栈空间，空间代价是 O(n)，哈希表的空间代价也是 O(n)，故空间复杂度也是 O(n)。

class Solution {
public:
    map<TreeNode*,int> m;
    int rob(TreeNode* root) { 
        if(!root)
            return 0;
        if(m[root]>0)
            return m[root];
        int s1=root->val;
        if(root->left)
        {
            s1+=rob(root->left->left)+rob(root->left->right);
        }
        if(root->right)
        {
            s1+=rob(root->right->left)+rob(root->right->right);
        }
        int s2=rob(root->left)+rob(root->right);
        m[root]=max(s1,s2);
        return m[root];
    }
};

思路三：优化动态规划
上面的方法每次保存的值为最大值，不确定是否偷该节点，还要访问孙子节点。为了简化，我们可以设计一个结构，表示某个节点的f(偷)和 g (不偷)值，在每次递归返回的时候，都把这个点对应的f(偷)和 g (不偷)返回给上一级调用，这样可以省去哈希表的空间。将每个节点偷与不偷能达到的最大金额保存为一个pair。同样，也是分两种情况：
1、偷该点
那么不能偷其左右节点；
2、不偷该点
可以偷其左右节点，也可以不偷其左右节点，按照最大值。

class Solution {
public:
    int rob(TreeNode* root) { 
        if(!root)
            return 0;
        return max(dfs(root).first,dfs(root).second);
    }
    pair<int,int> dfs(TreeNode* root){
        pair<int,int> result={0,0};
        if(!root)
            return result;
        pair<int,int> Left=dfs(root->left);
        pair<int,int> Right=dfs(root->right);
        result.first=max(Left.first,Left.second)+max(Right.first,Right.second);
        result.second=root->val+Left.first+Right.first;
        return result;
    }
};

时间复杂度：O(n)。上文中已分析。
空间复杂度：O(n)。虽然优化过的版本省去了哈希表的空间，但是栈空间的使用代价依旧是 O(n），故空间复杂度不变。

最后编辑于：2021.04.10 16:34:21