文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接198.打家劫舍2、题目描述二、个人思路整理1、思路分析本题的核心约束是两间相邻的房屋不能在同一晚上被偷。这是一个标准的线性动态规划问题。状态定义定义数组 dp[i] 表示偷窃前i ii间房屋下标范围[ 0 , i − 1 ] [0, i-1][0,i−1]所能获得的最大金额。数组长度开为n 1 n 1n1方便处理边界条件n nums.size() n \text{nums.size()}nnums.size()。边界条件d p [ 0 ] 0 dp[0] 0dp[0]0没有房屋可偷时最大金额为 0。d p [ 1 ] n u m s [ 0 ] dp[1] nums[0]dp[1]nums[0]只有 1 间房屋时最大金额就是第一间房的金额。状态转移方程对于第i ii间房对应数组中的金额为n u m s [ i − 1 ] nums[i-1]nums[i−1]其中i ≥ 2 i \ge 2i≥2面临两种选择不偷第i ii间房最大收益等于前i − 1 i-1i−1间房的最大收益即d p [ i − 1 ] dp[i-1]dp[i−1]。偷第i ii间房因为相邻限制不能偷第i − 1 i-1i−1间房最大收益为前i − 2 i-2i−2间房的最大收益加上当前房间金额即d p [ i − 2 ] n u m s [ i − 1 ] dp[i-2] nums[i-1]dp[i−2]nums[i−1]。两者取最大值d p [ i ] max ⁡ ( d p [ i − 1 ] , d p [ i − 2 ] n u m s [ i − 1 ] ) dp[i] \max(dp[i-1], dp[i-2] nums[i-1])dp[i]max(dp[i−1],dp[i−2]nums[i−1])最终结果dp[n]即为考虑全部n nn间房屋后能偷到的最大金额。2、解题代码classSolution{public:introb(vectorintnums){intnnums.size();// 边界情况若数组为空直接返回 0if(n0){return0;}if(n1){returnnums[0];}// dp[i] 表示面对前 i 间房屋时能够偷窃到的最高金额// 长度设为 n 1dp[0] 方便作为哨兵表示 0 建房间的情况vectorintdp(n1,0);// 初始化边界状态dp[0]0;// 0 间房收益为 0dp[1]nums[0];// 1 间房收益为 nums[0]// 状态递推计算for(inti2;in;i){// 选择一不偷当前房屋nums[i-1]收益继承 dp[i-1]// 选择二偷当前房屋则不能偷第 i-1 间房收益为 dp[i-2] nums[i-2]dp[i]max(dp[i-1],dp[i-2]nums[i-1]);}// 最终面对全部 n 间房时的最大金额returndp[n];}};复杂度分析时间复杂度O ( n ) O(n)O(n)。算法仅需从2 22到n nn进行一次单重循环每次状态计算为常数级操作因此运行时间与房屋数量n nn呈线性关系。空间复杂度O ( n ) O(n)O(n)。开辟了一个大小为n 1 n 1n1的动态规划数组dp来存储所有子问题的最优解。三、知识风暴动态规划Dynamic Programming是本题的核心算法思想。它通过将原问题拆解为若干相互重叠的子问题并利用「最优子结构」性质自底向上地递推求解最终得到全局最优解。对于「打家劫舍」这类具有明显阶段性和状态转移关系的线性问题动态规划能以O ( n ) O(n)O(n)的复杂度高效求解。算法核心思想最优子结构偷窃前i ii间房屋的最大金额可以由前i − 1 i-1i−1间和前i − 2 i-2i−2间房屋的最优解递推得到。每一步的局部最优决策偷或不偷当前房屋都能直接推导出全局最优解。无后效性一旦d p [ i − 1 ] dp[i-1]dp[i−1]和d p [ i − 2 ] dp[i-2]dp[i−2]确定后续的决策只依赖这两个状态与更早的偷窃方案无关。这保证了递推过程的正确性。状态转移核心转移方程为d p [ i ] max ⁡ ( d p [ i − 1 ] , d p [ i − 2 ] n u m s [ i − 1 ] ) dp[i] \max(dp[i-1], dp[i-2] nums[i-1])dp[i]max(dp[i−1],dp[i−2]nums[i−1])即「不偷当前房屋」与「偷当前房屋」两种选择取最大值。常见对比动态规划 vs 贪心动态规划时间复杂度O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)可优化为O ( 1 ) O(1)O(1)。适合每一步的决策依赖多个历史状态、且需要比较不同选择结果的场景通用性强。贪心算法时间复杂度O ( n ) O(n)O(n)空间复杂度O ( 1 ) O(1)O(1)。适合每一步的局部最优能直接决定全局最优的场景代码更简洁但适用范围较窄。共同点两者都依赖「最优子结构」性质。区别在于动态规划需要维护一张状态表来记录所有子问题的最优解而贪心只保留一个当前最优状态。动态规划的设计思想核心思想将大问题分解为一系列小问题先求解小问题的最优解再逐步组合成大问题的最优解。本题中从「只有 0 间房」「只有 1 间房」的边界情况出发逐步递推到「全部n nn间房」。与本题的联系打家劫舍问题的「相邻不能同偷」约束天然形成了「偷第i ii间则必须跳过第i − 1 i-1i−1间」的递推关系。我们只需维护前两个状态即可完成递推无需回溯。注意事项动态规划并不总是需要完整的状态表。本题中由于d p [ i ] dp[i]dp[i]只依赖d p [ i − 1 ] dp[i-1]dp[i−1]和d p [ i − 2 ] dp[i-2]dp[i−2]可以用两个滚动变量替代数组将空间复杂度从O ( n ) O(n)O(n)优化到O ( 1 ) O(1)O(1)。使用要点状态定义dp[i]表示偷窃前i ii间房屋下标范围[ 0 , i − 1 ] [0, i-1][0,i−1]所能获得的最大金额数组长度开为n 1 n 1n1以方便处理边界。边界初始化dp[0] 0无房可偷dp[1] nums[0]只有一间房时直接偷。递推更新从i 2 i 2i2到n nn每次计算dp[i] max(dp[i-1], dp[i-2] nums[i-1])比较「不偷」与「偷」两种选择的收益。结果返回递推结束后dp[n]即为考虑全部n nn间房屋后能偷到的最大金额。算法变体与扩展打家劫舍 IILeetCode 213房屋围成一圈首尾不能同时偷。解法是将问题拆分为「不偷第一间」和「不偷最后一间」两个子问题分别套用本题的线性 DP 后取最大值。打家劫舍 IIILeetCode 337房屋呈二叉树结构需在树上做动态规划。每个节点维护「偷该节点」与「不偷该节点」两种状态自底向上递推。使用最小花费爬楼梯LeetCode 746同样是线性 DP状态转移为「从上一级或上上级到达当前级的最小花费」与本题的递推模式高度相似。最长递增子序列LeetCode 300经典的线性 DP 问题通过维护以每个位置结尾的最长递增子序列长度来求解与本题共享「状态表递推」的核心模式。相关 LeetCode 例题213. 打家劫舍 II环形数组 线性 DP337. 打家劫舍 III树形 DP 状态机746. 使用最小花费爬楼梯线性 DP 状态转移198. 打家劫舍本题线性 DP 滚动优化