打家劫舍

题目链接: https://leetcode.cn/problems/house-robber/

解题思路：

1. 报警条件,连续偷了两间房

2. 设定一维dp数组,dp[i]表示到了第i间房偷窃到的最大金额,不一定偷了第i间房

3. 状态转移方程:dp[i]=max(dp[i-2]+nums[i],dp[i-1])

4. dp[i-2]+nums[i]表示不偷上一家获取到的最大金额

5. dp[i-1]表示当前房屋不偷获取的最大金额

6. dp[0]=0表示没有偷，dp[1]表示偷了第一家房子也就是nums[0]

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

复杂度分析

• 时间复杂度： 时间复杂度是 $O(n)$

• 空间复杂度： 空间复杂度是 $O(n)$