动态规划
返回两个状态
尝试动态规划
问题存在子问题结构，首先考虑动态规划
在从父节点向子节点传递状态的过程中，存在信息丢失和重复结算，可以考虑使用map保存局部计算结果
动态规划 + 局部计算结果
动态规划 + 多状态
robRoot(root)[0]: maximum value if root got not robbed
robRoot(root)[1]: maximum value if root got robbed
robRoot(root)[0] = max(robRoot(root.left)[0], robRoot(root.left)[1]) + max(robRoot(root.right)[0], robRoot(root.right)[1])
robRoot(root)[1] = root.val + robRoot(root.left)[0] + robRoot(root.right)[0]
LeetCode 337. House Robber III Description The thief has ...
题目 The thief has found himself a new place for his thieve...
问题描述 The thief has found himself a new place for his thie...
需要memo
The thief has found himself a new place for his thievery ...
这次贼要抢二叉树了。相邻的节点不能被抢还是利用之前的思想。是否要抢当前的节点由他的子节点和子子节点决定。
key tips 动态规划返回两个状态 algorithm 1 尝试动态规划问题存在子问题结构，首先考虑动态规划在...
The thief has found himself a new place for his thievery ...
The thief has found himself a new place for his thievery ...
本文标题：337. House Robber III
本文链接：https://www.haomeiwen.com/subject/opzuahtx.html
网友评论