198.打家劫舍

public class Solution {public int Rob(int[] nums) {if(nums.Length==0){return 0;}if(nums.Length==1){return nums[0];}int[] dp=new int[nums.Length+1];dp[0]=nums[0];dp[1]=Math.Max(nums[0],nums[1]);for(int i=2;i<nums.Length;i++){dp[i]=Math.Max(dp[i-2]+nums[i],dp[i-1]);}return dp[nums.Length-1];
}
}

Dp數組先排除Nums的特殊情況，然后分析是偷當前和上兩個還是偷前一個更大，誰大取誰。

213.打家劫舍II

public class Solution {public int Rob(int[] nums) {int[] dp=new int[nums.Length+1];if(nums.Length==0){return 0;}if(nums.Length==1){return nums[0];}return Math.Max(fun(nums,0,nums.Length-1),fun(nums,1,nums.Length));}public  int fun(int[]nums,int st,int ed){int x=0;int y=0;int z=0;for(int i=st;i<ed;i++){y=z;z=Math.Max(y,x+nums[i]);x=y;}return z;}
}

成環的情況就分成兩種單獨的打家劫舍1的題做就行，第一種是包含頭不包含尾，第二種是包含尾不包含頭，最后誰大取誰。

337.打家劫舍III

/*** Definition for a binary tree node.* public class TreeNode {*     public int val;*     public TreeNode left;*     public TreeNode right;*     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
public class Solution {public int Rob(TreeNode root) {int[] res=dfs(root);return Math.Max(res[0],res[1]);}public int[] dfs(TreeNode root){if(root==null){return new int[]{0,0};}int[] left=dfs(root.left);int[] right=dfs(root.right);int[] dp=new int[2];dp[0]=Math.Max(left[0],left[1])+Math.Max(right[0],right[1]);dp[1]=root.val+left[0]+right[0];return dp;}
}

考慮當前節點取不取，如果不取當前節點就考慮左節點取與不取的最大值，右節點取與不取的最大值，如果當前節點要取則左右節點不能取，采用后序遍歷來實現該題。