动态规划是算法学习的难点，而LeetCode的“打家劫舍”问题则是掌握其思想的绝佳切入点。通过这个经典案例，可以从最直观的暴力解法出发，一步步推导出高效的状态转移方程，并最终实现空间优化，从而深刻理解动态规划如何将复杂问题拆解为可重复计算的子问题。
智能速览
题目核心是在不相邻房屋的限制下求最大抢劫金额。
动态规划通过拆解子问题，决定每个房屋“抢”或“不抢”。
核心在于推导出max(nums[i] + dp[i-2], dp[i-1])的状态转移方程。
算法可进一步优化，仅用两个变量替代数组实现O(1)空间复杂度。
精华内容
理解动态规划的关键在于找到问题的递推关系。下面将以“打家劫舍”问题为例，从暴力解法逐步推导到最优解，揭示动态规划的核心思想。
暴力解法与局限
初期最直观的思路是使用决策树进行暴力搜索。对于每一间房屋，都存在“抢劫”或“不抢劫”两种选择，这会形成一个二叉树结构，枚举出所有可能的抢劫组合。虽然这种方法能够找到正确答案，但其时间复杂度高达O(2^n)，当房屋数量增多时，计算量会呈指数级增长，完全无法满足实际需求。
状态转移方程
动态规划的精髓在于识别并利用子问题。对于第i间房屋，其最大收益仅取决于前两间房屋的状态。具体而言，面临两个选择：一是抢劫第i间房屋，那么就不能抢第i-1间，此时收益为nums[i] + dp[i-2]；二是不抢第i间房屋，此时收益为dp[i-1]。因此，状态转移方程为 dp[i] = max(nums[i] + dp[i-2], dp[i-1])。这个方程是整个算法的核心，它将全局问题分解为了局部最优解的叠加。
空间优化与实现
观察状态转移方程可以发现，计算dp[i]时仅需要dp[i-1]和dp[i-2]的值，这意味着我们无需维护一个完整的DP数组。通过引入两个变量，例如rob1和rob2，分别记录dp[i-2]和dp[i-1]的值，在迭代过程中不断更新它们，即可得到最终结果。这种优化将空间复杂度从O(n)降至O(1)，是面试中的加分项。在Python中，这可以通过一次遍历和简洁的变量交换实现。
“打家劫舍”问题不仅是LeetCode上的一道高频题，更是理解动态规划思想的基石。掌握了从暴力解到状态转移方程，再到空间优化的全过程，就为解决更复杂的DP问题打下了坚实基础。你是否也通过这道题对动态规划有了新的认识？
