C++算法题解：房屋盗窃最大金额

这篇文章将讲解如何使用C++解决一个经典的算法问题：房屋盗窃。

问题描述：

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

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

示例：

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

提示：

1 <= nums.length <= 100* 0 <= nums[i] <= 400

解题思路：

这是一个典型的动态规划问题。我们可以使用动态规划的思想来解决。

定义状态： 假设 dp[i] 表示偷取前 i 个房屋能够获得的最高金额。2. 状态转移方程： 对于第 i 个房屋，有两种选择： * 偷取第 i 个房屋： 则前一个房屋（第 i-1 个房屋）不能偷取，所以偷取前 i 个房屋能够获得的最高金额是 dp[i-2] + nums[i]。 * 不偷取第 i 个房屋： 则偷取前 i 个房屋能够获得的最高金额是 dp[i-1]。因此，状态转移方程为： dp[i] = max(dp[i-2] + nums[i], dp[i-1])3. 边界条件： * dp[0] = nums[0] （只有一间房屋，只能偷取这间） * dp[1] = max(nums[0], nums[1]) （有两间房屋，选择金额较大的一间）4. 最终结果： dp[nums.size()-1] （表示偷取完所有房屋后能获得的最大金额）

**C++代码：**cpp#include #include

using namespace std;

int rob(vector& nums) { int n = nums.size(); if (n == 0) return 0; if (n == 1) return nums[0]; vector dp(n, 0); dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for (int i = 2; i < n; i++) { dp[i] = max(dp[i-2] + nums[i], dp[i-1]); } return dp[n-1];}

代码解释:

代码首先处理了房屋数量为 0 或 1 的特殊情况。* 然后，创建了一个 dp 数组来存储每个状态的结果。* 使用状态转移方程计算 dp 数组的值。* 最后返回 dp[n-1]，即为最终结果。

通过以上代码，就可以计算出不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。