当前位置：首页 > news >正文

动态规划实战：打家劫舍系列全解析

news 2026/5/29 23:49:27

一、题型整体分析

打家劫舍系列核心规则：不能偷窃相邻房屋，求能获取的最大金额。属于典型一维线性 DP，在斐波那契递推逻辑上增加条件判断，分三个主流版本：基础版、环形房屋、树形房屋。

DP 通用四步法依旧适用：状态定义 → 初始化 → 状态转移 → 结果输出

二、版本 1：基础打家劫舍（LeetCode 198）

题目描述

给定一维数组，每个元素代表房屋金额，相邻房屋不能同时偷窃，求偷窃的最大总金额。

步骤推导

状态定义dp[i]：偷窃前i间房屋能得到的最大金额
状态转移方程

偷第i间：则第i-1间不能偷，总金额 =dp[i-2] + nums[i-1]
不偷第i间：总金额 =dp[i-1]
最终取两者最大值：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])

初始边界

dp[0] = 0：无房屋，金额为 0
dp[1] = nums[0]：只有一间房，直接偷它

完整代码（DP 数组版）

#include <iostream> #include <vector> #include <algorithm> using namespace std; int rob(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; if(n == 1) return nums[0]; vector<int> dp(n + 1); dp[0] = 0; dp[1] = nums[0]; for(int i = 2; i <= n; ++i) { dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]); } return dp[n]; }

空间优化版（O (1) 空间）

仅依赖前两个状态，用变量替代数组，刷题首选：

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

三、版本 2：环形房屋（LeetCode 213）

题目变化

房屋围成环形，第一间和最后一间也视为相邻，不能同时偷窃。

解题思路

环形问题拆解为两个线性子问题，取最大值：

不偷第一间：偷窃范围nums[1] ~ nums[n-1]
不偷最后一间：偷窃范围nums[0] ~ nums[n-2]复用基础版代码，分别计算两个区间结果，返回较大值。

完整代码

// 复用基础版逻辑，指定左右区间 int robRange(vector<int>& nums, int l, int r) { int pre2 = 0, pre1 = 0, cur = 0; for(int i = l; i <= r; ++i) { cur = max(pre1, pre2 + nums[i]); pre2 = pre1; pre1 = cur; } return pre1; } int robCircle(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; if(n == 1) return nums[0]; // 两种情况取最大 return max(robRange(nums, 0, n-2), robRange(nums, 1, n-1)); }

四、版本 3：二叉树房屋（LeetCode 337）

题目变化

房屋以二叉树形式排列，不能偷窃父子节点，求最大金额。结合二叉树 + 动态规划 + 递归，属于树形 DP 入门。

状态定义（每个节点维护两个状态）

dp[0]：不偷当前节点，子节点可偷 / 可不偷，取最大值
dp[1]：偷当前节点，左右子节点都不能偷

状态转移

偷当前节点：dp[1] = root->val + left[0] + right[0]
不偷当前节点：dp[0] = max(left[0], left[1]) + max(right[0], right[1])

完整代码

struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 返回数组：[不偷当前节点最大值, 偷当前节点最大值] vector<int> dfs(TreeNode* root) { if(!root) return {0, 0}; vector<int> left = dfs(root->left); vector<int> right = dfs(root->right); // 偷当前节点 int robCur = root->val + left[0] + right[0]; // 不偷当前节点 int notRobCur = max(left[0], left[1]) + max(right[0], right[1]); return {notRobCur, robCur}; } int robTree(TreeNode* root) { vector<int> res = dfs(root); return max(res[0], res[1]); }

五、三类题型核心对比

表格

题型	特点	解题核心
线性房屋	首尾不相邻	基础一维 DP，相邻不能选
环形房屋	首尾相邻	拆分为两个线性区间，取最大值
树形房屋	父子节点相邻	树形 DP，每个节点维护「偷 / 不偷」双状态