198. 打家劫舍

https://leetcode-cn.com/problems/house-robber/

//dp动态规划，dp[i] 状态表示0-i家的盗的得最大值。那么dp[i] = (dp[i-1],dp[i-2]+nums[i])
//第i家不偷，或者第i家偷，就这两种子问题。
func rob(nums []int) int {
n := len(nums)
if n == 0{
return 0
}
dp := make([]int,n)
dp[0] = nums[0]
if n>=2{
dp[1] = MAX(nums[0],nums[1])
}
for i:=2;i<n;i++{
dp[i] = MAX(dp[i-1],dp[i-2]+nums[i])
}
return dp[n-1]
}

func MAX(i,j int) int{
if i<j{
return j
}else{
return i
}
}

　　优化 下存储空间

//dp动态规划，dp[i] 状态表示0-i家的盗的得最大值。那么dp[i] = (dp[i-1],dp[i-2]+nums[i])
//第i家不偷，或者第i家偷，就这两种子问题。
func rob(nums []int) int {
n := len(nums)
if n == 0{
return 0
}
curMax := 0
preMax := 0
for i:=0;i<n;i++{
tmp := curMax
curMax = Max(curMax,preMax+nums[i])
preMax = tmp
}
return curMax
}

func Max(i,j int) int{
if i<j{
return j
}else{
return i
}
}