题解

给定一个数组 $nums$ ，其中 $nums[i]$ 表示第 $i$ 个房屋中的现金。你是一个专业的小偷，在一夜之间计划偷窃这些房屋，但如果偷窃相邻的两个房屋就会触发报警系统。要求在不触动报警装置的前提下，求出一夜之内能够偷窃到的最高金额。

本题可以使用动态规划解决。我们定义数组 $dp$ ，其中 $dp[i]$ 表示偷到第 $i$ 个房屋时所能获得的最高金额。状态转移方程为

dp[i]=\max(dp[i-1],\ dp[i-2]+nums[i])

题目内容

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

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

一个代表每个房屋存放金额的非负整数数组

一个整数表示一夜之内能够偷窃到的最高金额。

输入

1 2 3 1

输出

偷窃 $1$ 号房屋 (金额 $= 1$ ) ，然后偷窃 $3$ 号房屋 (金额 $= 3$ )。

偷窃到的最高金额 $= 1 + 3 = 4$ 。

输入

2 7 9 3 1

输出

偷窃 $1$ 号房屋 (金额 $= 2$ ), 偷窃 $3$ 号房屋 (金额 = 9)，接着偷窃 $5$ 号房屋 (金额 $= 1$ )。

偷窃到的最高金额 $= 2 + 9 + 1 = 12$ 。

提示：