题解 | #打家劫舍(二)#

package main

import "fmt"

func _rob(arr []int) int {
	dp := make([]int, len(arr))
	dp[0] = arr[0]
	//相当于最前面还有一个房子价值=0
	dp[1] = max(arr[0], arr[1]+0)
	for i := 2; i < len(arr); i++ {
		dp[i] = max(dp[i-2]+arr[i], dp[i-1])
	}
	return dp[len(arr)-1]
}

func rob(arr []int) int {
	if len(arr) == 1 {
		return arr[0]
	}
	if len(arr) == 2 {
		return max(arr[0], arr[1])
	}
	return max(_rob(arr[:len(arr)-1]), _rob(arr[1:]))
}

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

/*
*
假设数组 nums 的长度为 n。
如果不偷窃最后一间房屋，则偷窃房屋的下标范围是 [0,n−2]；
如果不偷窃第一间房屋，则偷窃房屋的下标范围是 [1,n−1]

输入：nums = 1 2 3 1
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

输入：1 3 1 3 100
输出：103
*/
func main() {
	//arr := []int{1, 3, 1, 3, 100}
	var num int
	fmt.Scanln(&num)
	arr := make([]int, num)
	for i := 0; i< num; i++{
		fmt.Scan(&arr[i])
	}
	fmt.Println(rob(arr))
}