力扣题解-198. 打家劫舍（动态规划）

题目：198. 打家劫舍

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

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

示例 1： 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

示例 2： 输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示： 0 <= nums.length <= 100 0 <= nums[i] <= 400

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/house-robber 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

状态定义

dp[i]表示偷窃前i间房屋获取的最大金额。

状态转移方程

dp[i]有两种可能的方式得到：偷第i间房屋时获得（dp[i-2]（偷前i-2间房得到的最大金额） + nums[i]），不偷第i间房屋时获得（dp[i-1]）。

dp[i] = max(dp[i-2] + nums[i], dp[i-1])，i >= 2。

初始条件/边界

dp[0] = nums[0] dp[1] = max(nums[0], nums[1])

最优解

dp[n-1]

空间复杂度改进

由状态转移方程，当前状态只与前两个状态dp[i-1]和dp[i-2]有关，因此可用两个变量来缓存即可。

代码

class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); if (n == 0) { return 0; } if (n == 1) { return nums[0]; } int preTwo = nums[0]; int preOne = max(nums[0], nums[1]); for (int i = 2; i < n; i++) { int tmp = preOne; preOne = max(preOne, preTwo + nums[i]); preTwo = tmp; } return preOne; } };