leetcode 337. House Robber III DP动态规划 + DFS深度有限遍历

旧城等待， 2022-06-07 01:13 155阅读 0赞

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:  
3  
/ \\  
2 3  
\\ \\  
3 1  
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.  
Example 2:  
3  
/ \\  
4 5  
/ \\ \\  
1 3 1  
Maximum amount of money the thief can rob = 4 + 5 = 9.

这道题意很简单，就是父亲节点和自己不可以同时抢劫，这里设置一个返回数字res，其中res\[0\]表示抢劫当前节点， res\[1\]不抢劫当前节点，直接DFS递归遍历即可实现。

建议和这道题[leetcode 740. Delete and Earn 动态规划DP][leetcode 740. Delete and Earn _DP]、[leetcode 198. House Robber 入室抢劫 + DP求解][leetcode 198. House Robber _ _ DP] 和 这道题 [leetcode 213. House Robber II 入室抢劫 抢劫问题][leetcode 213. House Robber II _] 一起学习。

代码如下：

/*class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
    }*/
    
    
    /*
     * 这其实也是DP的解决方法之一，
     * */
    class Solution
    {
        public int rob(TreeNode root)
        {
            if(root==null)
                return 0;
    
            int []res=getRes(root);
            return Math.max(res[0], res[1]);
        }
    
        /*
         * res[0]表示抢劫当前节点的记录的最大值
         * res[1]表示不抢劫当前的结点的记录的最大值
         * */
        public int[] getRes(TreeNode root) 
        {
            int[] res=new int[2];
            if(root==null)
                return res;
            else 
            {
                int[] left=getRes(root.left);
                int[] right=getRes(root.right);
    
                //抢劫当前节点，然后不抢劫其子节点
                res[0]=root.val + left[1] + right[1];
                //不抢劫当前节点，然后可以抢劫或者不抢劫其子节点
                res[1]=Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
                return res;
            }
        }
    }

下面是C++的做法，和上面的思路一模一样

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        int rob(TreeNode* root)
        {
            vector<int> res = dfs(root);
            return max(res[0], res[1]);
        }
    
        vector<int> dfs(TreeNode* root)
        {
            vector<int> res(2, 0);
            if (root == NULL)
                return res;
            else
            {
                vector<int> left = dfs(root->left);
                vector<int> right = dfs(root->right);
    
                res[0] = root->val + left[1] + right[1];
                res[1] = max(left[0], left[1]) + max(right[0], right[1]);
                return res;
            }
    
        }
    };

[leetcode 740. Delete and Earn _DP]: http://blog.csdn.net/jackzhang_123/article/details/78895001
[leetcode 198. House Robber _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/78037840
[leetcode 213. House Robber II _]: http://blog.csdn.net/jackzhang_123/article/details/78050767