剑指 Offer II 089. 房屋偷盗

最值问题 动态规划
小偷可以从第一个位置开始也可以从任意一个开始
因为不能触发警报。只要不是相邻的都可以
1、偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k-2间房屋的最高总金额与第 k 间房屋的金额之和。

2、不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k间房屋能偷窃到的最高总金额。

func rob(_ nums: [Int]) -> Int {
        
        let length = nums.count
        if length == 1 {
            return nums[0]
        }
        var valueArray = Array.init(repeating: 0, count: length)
        valueArray[0] = nums[0]
        valueArray[1] = max(nums[0], nums[1])
        for i in 2..<length {
            valueArray[i] = max(valueArray[i - 2] + nums[i], valueArray[i - 1])

        }
        return valueArray.last ?? 0
    }