步驟一、確定遞歸函數的參數和返回值:

dp數組及下標的含義

dp數組的長度為2， 下標為0記錄不偷該節點所得到的的最大金錢，下標為1記 錄偷該節點所得到的的最大金錢。

步驟二、確定終止條件:

在遍歷的過程中， 如果遇到空節點，很明顯，無論偷還是不偷， 都是0 if not root: return [0, 0]
而這一步，就算dp的初始化

步驟三、確定遍歷順序:

對于樹的遍歷，一定要使用后序遍歷，要通過遞歸函數的返回值來做下 一步的計算

先遞歸左節點， 得到左節點偷與不偷的金錢 left = robTree(root.left)
再遞歸右節點， 得到右節點偷與不偷的金錢 right = robTree(root.right)

步驟四、確定單層的遞歸邏輯(動態轉移方程):

這個要分為當前節點偷或者不偷分別來討論

如果偷當前節點， 那么左右孩子就不能偷， val1 = root.val + left[0] + right[0]， 下標為0記錄不偷左右孩子的最大金錢

如果不偷當前節點，那么左右孩子可以考慮偷了， 但偷不偷呢， 選最大的那個 val2 = max(left)+max(right)

所以最后當前節點的狀態就是 [val2, val1]，所以到根節點的時候，返回 這倆最大的即可。

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def rob(self, root: TreeNode) -> int:if not root:return 0def robTree(root):if not root: # 遞歸終止return 0, 0# 遍歷leftchild_steal, leftchild_nosteal = robTree(root.left)rightchild_steal, rightchild_nosteal = robTree(root.right)# 如果偷當前節點則左右孩子不能偷steal = root.val + leftchild_nosteal + rightchild_nosteal# 如果不偷當前節點，那么左右孩子可以考慮偷lanosteal = max(leftchild_steal, leftchild_nosteal) + max(rightchild_steal, rightchild_nosteal)return steal, nostealreturn max(robTree(root))

總結

以上是生活随笔為你收集整理的104. Leetcode 337. 打家劫舍 III (动态规划-打家劫舍)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。