leetCode 198

问题

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
你是一个专业的盗贼，正准备沿着一条大街实施抢劫。每个房子都有一定的金钱，而相邻的两个房子的安保是连接的。如果两个房子在同一个晚上被抢劫，安保会自动报警。

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
使用正整数数组来表示每个房子的金钱，在不惊动警察情况下，你最多能抢到多少钱？

大概是这个意思吧。

思想

如果整条大街只有一间房子，显然：Max[1] = M[1]
如果整条大街只有两间房子，则: Max[2] = max(M[1], M[2])

假设有N个房子，第i个房子的金钱数用 M[i]来表示，而能获得最大的金钱数用Max[i]来表示。对于第i个房子，有两种选择：

• 抢劫 i ， 则说明了没有抢劫 i - 1， 所以金钱数为：Max[i - 2] + M[i]
• 不抢劫 i , 则金钱数为：Max[i - 1]
  对着两种情况进行比较，选择大者的方案进行。

实现

func rob(_ nums: [Int]) -> Int {
    if nums.count == 0 {
        return 0
    }
    else if nums.count == 1 {
        return  nums[0]
    }
    else if nums.count == 2 {
        return max(nums[0], nums[1])
    }
    else {
        var array = [Int]()
        
        array.append(nums[0])
        array.append(max(nums[0], nums[1]))
        
        for index in 2..<nums.count {
            // 动态规划，将前面的最大值都放在数组里面保存起来
            array.append(max(nums[index] + array[index - 2], array[index - 1]))
        }
        
        return array.last!
    }
}