别再死记 DP 了！一道「打家劫舍 III」，彻底看懂树形动态规划

别再死记 DP 了！一道「打家劫舍 III」，彻底看懂树形动态规划

很多人第一次刷到《打家劫舍 III》的时候，都会有一种熟悉又陌生的感觉。

熟悉的是：

“这不就是打家劫舍吗？”

陌生的是：

“怎么突然长树上去了？？？”

结果一看代码。
更懵。

什么：

• 后序遍历
• 树形 DP
• 状态转移
• dfs 返回数组

不少人看到这一步，直接退出页面。

但说实话。

这题其实非常有意思。

因为它真正难的地方，不是代码。

而是：

你能不能把“树”看成一种递归状态结构。

一旦想通这一层。

树形 DP 会瞬间开窍。

今天咱们就用最接地气的方式，彻底聊透这道经典题。

一、先别急着写代码，先理解“贼”的逻辑

题目大概是这样：

一个小偷准备偷东西。

但是：

如果偷了某个房子，就不能偷它的直接孩子节点。

因为会触发警报。

比如：

3 / \ 2 3 \ \ 3 1

如