线性动态规划：打家劫舍 题目描述 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素是不能偷窃相邻的房屋。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 示例： 输入：[ 2,7,9,3,1 ] 输出：12 解释：偷窃第1间（金额=2）、第3间（金额=9）和第5间（金额=1），总金额=2+9+1=12。 解题过程 1. 问题分析 目标：从一排房屋中选择若干不相邻的房屋进行偷窃，使得总金额最大。 约束：不能选择相邻的房屋（即如果选择了第i间房屋，则不能选择第i-1和第i+1间）。 关键点：每个房屋有"偷"或"不偷"两种选择，但选择受相邻关系限制。 2. 定义状态 我们定义状态 dp[i] 表示偷窃到第i间房屋（包括第i间）时能获得的最高金额。注意这里"偷窃到第i间"并不意味着一定要偷第i间，而是考虑前i间房屋的最优解。 更准确地说，我们可以定义： dp[i] ：考虑前i间房屋（从第1间到第i间）能偷窃到的最高金额 3. 状态转移方程 对于第i间房屋，我们有两种选择： 不偷第i间 ：那么最高金额等于前i-1间房屋的最高金额，即 dp[i-1] 偷第i间 ：那么不能偷第i-1间，最高金额等于前i-2间房屋的最高金额加上第i间的金额，即 dp[i-2] + nums[i] 因此，状态转移方程为： dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 4. 边界条件 当只有0间房屋时： dp[0] = 0 当只有1间房屋时： dp[1] = nums[0] （只能偷这一间） 当有2间房屋时： dp[2] = max(nums[0], nums[1]) （选择金额较大的那间） 5. 算法实现步骤 让我们用示例 [ 2,7,9,3,1 ] 来演示： 步骤1：初始化 dp[0] = 0 （没有房屋） dp[1] = 2 （只有第1间房屋） 步骤2：逐步计算 dp[2] = max(dp[1], dp[0] + nums[1]) = max(2, 0 + 7) = 7 dp[3] = max(dp[2], dp[1] + nums[2]) = max(7, 2 + 9) = 11 dp[4] = max(dp[3], dp[2] + nums[3]) = max(11, 7 + 3) = 11 dp[5] = max(dp[4], dp[3] + nums[4]) = max(11, 11 + 1) = 12 步骤3：得到结果 最终结果为 dp[5] = 12 6. 空间优化 由于每个状态只依赖于前两个状态，我们可以用两个变量代替整个dp数组： prev2 表示 dp[i-2] prev1 表示 dp[i-1] current 表示 dp[i] 这样可以将空间复杂度从O(n)降低到O(1)。 7. 算法总结 时间复杂度：O(n)，需要遍历一次数组 空间复杂度：O(1)，使用常数级别的额外空间 核心思想：通过动态规划记录每个位置的最优解，利用最优子结构性质逐步求解 这个算法优雅地解决了房屋抢劫问题，体现了动态规划"将复杂问题分解为简单子问题"的核心思想。