leetcode House Robber III

leetcode House Robber III

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:

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Maximum amount of money the thief can rob = 4 + 5 = 9.

题目地址:leetcode House Robber III

题意:给定一棵二叉树,求能获取的权值最大和(相邻的不能同时取)

思路: 树形dp

显然有:

  • rob_root = max(rob_L + rob_R , no_rob_L + no_nob_R + root.val)
  • no_rob_root = rob_L + rob_R

递归即可

Python:

C++

Java

 

 

 

本题是leetcode 337  House Robber III 题解,

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode House Robber III
本文地址:https://www.hrwhisper.me/leetcode-house-robber-iii/

您的支持将鼓励我继续创作!

Leetcode , , , , . permalink.

4 thoughts on “leetcode House Robber III

  1. rob_root = max(rob_L + rob_R , no_rob_L + no_nob_R + root.val)
    ————————————————————-
    抢根为什么要取最大?如果rob_L + rob_R比较大的话根不就没抢吗。 请解释一下,谢谢

    我觉得抢根应该是:rob_root = no_rob_L + no_rob_R + root.val
    不抢根应该是: max(rob_L,no_rob_L)+max(rob_R,no_rob_R)
    这样结果也是对的

Leave a Reply

Your email address will not be published. Required fields are marked *