动态规划之打家劫舍

题目

你是一个专业的小偷,计划偷窃沿街的房屋.每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警.

思路

第 n 个房屋时候的最大收益是:
第 n-1 时的最大收益
第 n-2 时的最大收益+第 n 个的收益

两者中的最大值

状态转移方程

nums[n] = max(nums[n-2]+nums[n],nums[n-1])

最终源码

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

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