題目

https://leetcode.com/problems/house-robber-iii/

---

思考：什么情況下 dp 需要強制包含當前元素？

dp 過程中，需要包含當前元素 的例子：

• leetcode 322. Coin Change | 322. 零錢兌換（動態規劃）
• leetcode 300. Longest Increasing Subsequence | 300. 最長遞增子序列（動態規劃）
• 算法設計與分析：0-1背包問題（動態規劃）

dp 過程中，不需要包含當前元素 的例子：

• leetcode 198. 打家劫舍（動態規劃）
• leetcode 213. House Robber II | 213. 打家劫舍 II（動態規劃）

當問題類似于 前綴和問題、背包問題 的時候，也就是 對 dp 數組的訪問是按照索引進行隨機訪問 的情況下，需要在每一個狀態上包含元素本身信息，所以這種情況下 通常強制包含當前元素。

而當問題類似于 打家劫舍 問題的時候，結果與被遍歷序列的前后順序有關，對 dp 數組的訪問只涉及到 i-1, i-2 等這些有限個數的相鄰下標（假設當前元素下標為 i），不需要對前面的 dp 數組進行隨機訪問，這時不需要存儲每一個狀態下的元素本身信息，通常不用強制包含當前元素。

---

題解

參考了：https://leetcode.com/problems/house-robber-iii/discuss/79330/Step-by-step-tackling-of-the-problem 的開頭，有了點思路，后面自己寫的。

可以看作是一個樹形 dp 問題，也可以參考：左神算法：找到二叉樹中的最大搜索二叉子樹（樹形dp套路，Java版）

class Solution {public int rob(TreeNode root) {if (root == null) return 0;rob(root.left);rob(root.right);int l, r, ll, lr, rl, rr;l = r = ll = lr = rl = rr = 0;if (root.left != null) {l = root.left.val;if (root.left.left != null) {ll = root.left.left.val;}if (root.left.right != null) {lr = root.left.right.val;}}if (root.right != null) {r = root.right.val;if (root.right.left != null) {rl = root.right.left.val;}if (root.right.right != null) {rr = root.right.right.val;}}// root.val 存儲【偷或不偷】當前元素時的最大值root.val = Math.max(root.val + ll + lr + rl + rr, l + r);return root.val;} }

總結

以上是生活随笔為你收集整理的leetcode 337. House Robber III | 337. 打家劫舍 III（树形dp；什么情况下dp需要强制包含当前元素？）的全部內容，希望文章能夠幫你解決所遇到的問題。

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