PHP刷题秘籍：一招搞定LeetCode经典动态规划问题

解锁算法新思路，让你的PHP技能再上一层楼！

大家好！今天我们来聊一聊如何在PHP中解决LeetCode上经典的动态规划问题——"打家劫舍"问题。这个问题看似简单，却蕴含着精妙的算法思想，非常适合用来提升我们的编程思维。

问题背景

想象一下，你是一个专业的小偷（当然只是在算法世界里！），计划偷窃沿街的房屋。每间房内都有一定现金，但有个限制：相邻的房屋装有防盗系统，如果相邻房屋在同一晚被闯入，系统会自动报警。

你的任务：在不触动警报的情况下，计算一夜能偷窃的最高金额。

示例解析

先看两个例子：

// 示例1
$nums1 = [1,2,3,1];
// 偷1号房(1) + 3号房(3) = 4

// 示例2  
$nums2 = [2,7,9,3,1];
// 偷1号房(2) + 3号房(9) + 5号房(1) = 12

常规思路：动态规划

大多数人的第一反应是用动态规划：

function rob($nums) {
    $n = count($nums);
    if ($n == 0) return 0;
    if ($n == 1) return $nums[0];
    
    $dp = [];
    $dp[0] = $nums[0];
    $dp[1] = max($nums[0], $nums[1]);
    
    for ($i = 2; $i < $n; $i++) {
        $dp[$i] = max($dp[$i-1], $dp[$i-2] + $nums[$i]);
    }
    
    return $dp[$n-1];
}

这种方法虽然正确，但需要O(n)的空间复杂度。有没有更优雅的解法呢？

进阶思路：状态机法

今天我要分享一个更巧妙的解法——状态机法，只需O(1)的空间复杂度：

function rob($nums) {
    $rob = 0;      // 偷当前房屋的最大金额
    $notRob = 0;   // 不偷当前房屋的最大金额
    
    foreach ($nums as $num) {
        // 偷当前房屋：之前不偷 + 当前房屋金额
        $currentRob = $notRob + $num;
        // 不偷当前房屋：取之前偷或不偷的最大值
        $currentNotRob = max($rob, $notRob);
        
        // 更新状态
        $rob = $currentRob;
        $notRob = $currentNotRob;
    }
    
    return max($rob, $notRob);
}

为什么这个解法如此优雅？

1. 状态定义清晰

• $rob：选择偷当前房屋时的最大收益
• $notRob：选择不偷当前房屋时的最大收益

2. 状态转移直观

• 要偷当前房屋，前一房屋必须不能偷（$notRob + $num）
• 不偷当前房屋，前一房屋可偷可不偷（max($rob, $notRob)）

3. 空间效率极高

只用了两个变量，无论输入数组多长，空间占用都是常数级。

实战演练

让我们手动推演一下示例1 [1,2,3,1]：

初始：rob=0, notRob=0

处理房屋1(1):
当前偷：notRob+1 = 0+1 = 1
当前不偷：max(0,0)=0
更新：rob=1, notRob=0

处理房屋2(2):
当前偷：notRob+2 = 0+2 = 2  
当前不偷：max(1,0)=1
更新：rob=2, notRob=1

处理房屋3(3):
当前偷：notRob+3 = 1+3 = 4
当前不偷：max(2,1)=2
更新：rob=4, notRob=2

处理房屋4(1):
当前偷：notRob+1 = 2+1 = 3
当前不偷：max(4,2)=4
更新：rob=3, notRob=4

最终结果：max(3,4) = 4

性能对比

扩展应用

这种状态机的思想不仅能解决"打家劫舍"问题，还能解决许多类似的约束问题：

1. 环形房屋：第一间和最后一间相邻
2. 二叉树房屋：房屋呈树形结构
3. 股票买卖问题：含冷冻期的买卖策略

学习要点

1. 识别问题特征：当问题涉及"相邻约束"时，考虑状态机
2. 定义清晰状态：明确每个状态代表的含义
3. 设计状态转移：理清状态间的转换关系
4. 优化空间：思考能否减少空间使用

总结

算法学习不是死记硬背，而是要理解背后的思想。状态机法给我们提供了一个全新的视角来看待动态规划问题。

记住：优秀的代码不仅追求正确性，还要追求简洁和高效。下次遇到类似问题时，不妨试试状态机的思路！