dp[i]表示偷第i家及之前所能獲取的最大金額
偷第i家：dp[i] = dp[i-2]+nums[i]，不偷第i家：dp[i] = dp[i-1]

func rob(nums []int) int {if len(nums) == 0 {return 0}if len(nums) == 1 {return nums[0]}dp := make([]int, len(nums))dp[0] = nums[0]dp[1] = max(nums[0], nums[1])for i := 2; i < len(nums); i++ {dp[i] = max(dp[i-1], dp[i-2]+nums[i])}return dp[len(nums) - 1]
}

因為搶劫到的最高金額只與前兩間房屋有關，故采用滾動數組優化

first := nums[0]second := max(nums[0], nums[1])for i := 2; i < len(nums); i++ {temp := secondsecond = max(first+nums[i], second)first = temp}return second

上題擴展：房屋是環狀的，意味著第一個房子和最后一個房子不能同時偷，故求解max(不偷第一個房子，不偷最后一個房子)

func rob(nums []int) int {if len(nums) == 0 {return 0}if len(nums) == 1 {return nums[0]}if len(nums) == 2 {return max(nums[0], nums[1])}return max(rob1(nums[1:]), rob1(nums[:len(nums)-1]))
}func rob1(nums []int) int {first := nums[0]second := max(nums[0], nums[1])for i := 2; i < len(nums); i++ {temp := secondsecond = max(first+nums[i], second)first = temp}return second
}

后序遍歷：通過遞歸函數的返回值進行下一步求解
偷當前節點，則當前節點的左右孩子都不能偷；不偷當前節點，則當前節點的左右孩子可偷可不偷，取兩種可能性的最大值。

func rob(root *TreeNode) int {var help func(root *TreeNode) (int, int)help = func(root *TreeNode) (int, int) {if root == nil {return 0, 0}leftRob, leftNoRob := help(root.Left)rightRob, rightNoRob := help(root.Right)rob := root.Val + leftNoRob + rightNoRobnoRob := max(leftRob, leftNoRob) + max(rightRob, rightNoRob)return rob, noRob}return max(help(root))
}