[leetcode 337]打败了100%的解法

发表于 更新于

题目概述

原题链接

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.

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

最快的解法

以下代码打败了100%的其它python3解法。 带记忆体的递归，也就是动态规划。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:

    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.memo = {}
        return self.dp(root)

    def dp(self, root):
        if root is None:
            return 0
        else:
            if root in self.memo :
                return self.memo[root]

            v1 = self.dp(root.left) + self.dp(root.right)

            v2 = root.val
            if root.left is not None:
                v2 += self.dp(root.left.left) + self.dp(root.left.right)
            if root.right is not None:
                v2 += self.dp(root.right.left) + self.dp(root.right.right)
            self.memo[root] = max(v1, v2)
            return self.memo[root]

截图留念

1
2
              You are Here!
Your runtime beats 100.00% of python3 submissions.

robber3_submit_result