LeetCode:

198. 打家劫舍 - 力扣（LeetCode）

1.思路

邊界思維，只有一個(gè)元素和兩個(gè)元素的初始化考慮
當(dāng)元素?cái)?shù)大于3個(gè)時(shí)，
逆向思維，是否偷最后一個(gè)元素，倒序得出遞推公式dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);前者不偷，后者偷，兩者取較大值。

2.代碼實(shí)現(xiàn)

 1//?遞推公式逆向思考可以得出2class?Solution?{3????public?int?rob(int[]?nums)?{4????????int?len?=?nums.length;5????????if?(len?==?0)?{6????????????return?0;7????????}?else?if?(len?==?1)?{8????????????return?nums[0];9????????}
10
11????????int[]?dp?=?new?int[len];
12????????dp[0]?=?nums[0];
13????????dp[1]?=?Math.max(dp[0],?nums[1]);
14
15????????for?(int?i?=?2;?i?<?len;?i++)?{
16????????????dp[i]?=?Math.max(dp[i?-?1],?dp[i?-?2]?+?nums[i]);
17????????}
18????????return?dp[len?-?1];
19????}
20}
21//?滾動(dòng)數(shù)組，有些小坑得踩一下
22class?Solution?{
23????public?int?rob(int[]?nums)?{
24????????int?len?=?nums.length;
25
26????????if?(len?==?0)?{
27????????????return?0;
28????????}?else?if?(len?==?1)?{
29????????????return?nums[0];
30????????}?else?if?(len?==?2)?{
31????????????return?Math.max(nums[0],?nums[1]);
32????????}
33
34????????int[]?result?=?new?int[3];
35????????result[0]?=?nums[0];
36????????result[1]?=?Math.max(nums[0],?nums[1]);
37
38????????for?(int?i?=?2;?i?<?len;?i++)?{
39????????????result[2]?=?Math.max(result[0]?+?nums[i],?result[1]);
40
41????????????result[0]?=?result[1];
42????????????result[1]?=?result[2];
43????????}
44????????return?result[2];
45????}
46}

3.復(fù)雜度分析

時(shí)間復(fù)雜度：O(n).
空間復(fù)雜度：O(1).

LeetCode:

213. 打家劫舍 II - 力扣（LeetCode）

1.思路

考慮首元素和不考慮首元素，即可將環(huán)形進(jìn)行拆解為兩個(gè)線性數(shù)組，取兩者之間的較大值即可

2.代碼實(shí)現(xiàn)

 1class?Solution?{2????public?int?rob(int[]?nums)?{3????????if?(nums?==?null?||?nums.length?==?0)?{4????????????return?0;5????????}67????????int?len?=?nums.length;8????????if?(len?==?1)?{9????????????return?nums[0];
10????????}
11????????return?Math.max(robAction(nums,?0,?len?-?1),?robAction(nums,?1,?len));
12????}
13
14????int?robAction(int[]?nums,?int?start,?int?end)?{
15????????int?x?=?0,?y?=?0,?z?=?0;
16????????for?(int?i?=?start;?i?<?end;?i++)?{
17????????????y?=?z;
18????????????z?=?Math.max(y,?x?+?nums[i]);?//
19????????????x?=?y;
20????????}
21????????return?z;
22????}
23}

3.復(fù)雜度分析

時(shí)間復(fù)雜度：O(n).
空間復(fù)雜度：O(1).

LeetCode:

337. 打家劫舍 III - 力扣（LeetCode）

1.思路

分兩種情況，選擇根節(jié)點(diǎn)和不選根節(jié)點(diǎn)，分別計(jì)算兩種情況的較大值，并選擇兩者之間的較大值存入map集合中，返回結(jié)果。

2.代碼實(shí)現(xiàn)

 1/**2?*?Definition?for?a?binary?tree?node.3?*?public?class?TreeNode?{4?*?????int?val;5?*?????TreeNode?left;6?*?????TreeNode?right;7?*?????TreeNode()?{}8?*?????TreeNode(int?val)?{?this.val?=?val;?}9?*?????TreeNode(int?val,?TreeNode?left,?TreeNode?right)?{
10?*?????????this.val?=?val;
11?*?????????this.left?=?left;
12?*?????????this.right?=?right;
13?*?????}
14?*?}
15?*/
16class?Solution?{
17????public?int?rob(TreeNode?root)?{
18????????//?創(chuàng)建一個(gè)?Map?來保存已經(jīng)計(jì)算過的節(jié)點(diǎn)的最大金額
19????????Map<TreeNode,?Integer>?map?=?new?HashMap<>();?
20????????//?調(diào)用遞歸方法計(jì)算能夠偷取的最大金額
21????????return?robAction(root,?map);
22????}
23????//?構(gòu)建遞歸方法，計(jì)算以?root?為根節(jié)點(diǎn)的子樹能夠偷取的最大金額
24????int?robAction(TreeNode?root,?Map<TreeNode,?Integer>?map)?{
25????????//?如果?root?為空，返回?0
26????????if?(root?==?null)?{
27????????????return?0;
28????????}?
29????????//?如果map中已經(jīng)存在以?root?為根節(jié)點(diǎn)的子樹的最大金額，直接返回該值
30????????if?(map.containsKey(root))?{
31????????????return?map.get(root);
32????????}
33????????//?money?來保存以?root?為根節(jié)點(diǎn)的子樹能夠偷取的最大金額
34????????int?money?=?root.val;
35????????//?左：判斷?root?的左子節(jié)點(diǎn)是否存在，存在則計(jì)算左子節(jié)點(diǎn)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的最大金額并加到?money?中
36????????if?(root.left?!=?null)?{
37????????????money?+=?robAction(root.left.left,?map)?+?robAction(root.left.right,?map);
38????????}
39????????//?右：同理
40????????if?(root.right?!=?null)?{
41????????????money?+=?robAction(root.right.left,?map)?+?robAction(root.right.right,?map);
42????????}
43????????//?結(jié)果從選擇根節(jié)點(diǎn)和不選擇根節(jié)點(diǎn)之中選取最大值
44????????int?res?=?Math.max(money,?robAction(root.left,?map)?+?robAction(root.right,?map));
45????????//?將結(jié)果res?存入map中，以便下次使用
46????????map.put(root,?res);
47????????return?res;
48????}
49}

3.復(fù)雜度分析

時(shí)間復(fù)雜度：O(n).
空間復(fù)雜度：O(logn).