198.打家劫舍

动态规划

考虑当前房屋偷还是不偷。同时当前房屋的状态只与前一间房屋有关，所以可以用滚动数组进行空间优化。

时间复杂度：O(N)
空间复杂度：O(1)

func rob(nums []int) int {
    dp := make([]int, 2)
    dp[0] = 0
    dp[1] = 0

    for i := 1; i <= len(nums); i++ {
        temp := dp[0]
        dp[0] = max(dp[1], dp[0])
        dp[1] = temp + nums[i-1]
    }

    return max(dp[0], dp[1])
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}