文章目錄

• 題目描述
• 思路 & 代碼
• • • 更新版

題目描述

• 這年頭當(dāng)個小偷，都得會 dp 和二叉樹了
• 和前面的 I & II 有點不同，這次直接換了數(shù)據(jù)結(jié)構(gòu)，寫樹來了。（之后不會是圖吧）
• 很厲害，第一次接觸到樹型的dp，一聽就特別不同凡響
  

思路 & 代碼

• 返回值分成兩部分，一個是當(dāng)前 root 偷了的情況，一個是沒偷的情況
• 狀態(tài)轉(zhuǎn)移方程、最優(yōu)子結(jié)構(gòu)、邊界見代碼
• 時間復(fù)雜度 O(n)，空間復(fù)雜度 O(n)

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/ class Solution {public int rob(TreeNode root) {// 0：當(dāng)前結(jié)點未取 1：當(dāng)前結(jié)點取了int[] result = forRob(root);return Math.max(result[0], result[1]);}int[] forRob(TreeNode root){// 邊界if(root == null){return new int[2];}int[] result = new int[2];// 最優(yōu)子結(jié)構(gòu)int[] right = forRob(root.right);int[] left = forRob(root.left);// 狀態(tài)轉(zhuǎn)移方程// root 沒偷的情況：左右結(jié)點可偷，也可不偷result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);// root 偷了的情況：左右結(jié)點一定不偷result[1] = root.val + left[0] + right[0];return result;} }

更新版

• 自底向上，狀態(tài)轉(zhuǎn)移方程是重點，思路可以看上面代碼的注釋。

class Solution {public int rob(TreeNode root) {int[] ans = robTree(root);return Math.max(ans[0], ans[1]);}public int[] robTree(TreeNode root) {if(root == null) {return new int[]{0, 0};}int[] left = robTree(root.left);int[] right = robTree(root.right);int[] now = new int[2];now[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);now[1] = root.val + left[0] + right[0];return now;} } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】337. 打家劫舍III（Java、树型动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。