本文共 2460 字，大约阅读时间需要 8 分钟。

小偷偷房子的问题可以通过动态规划和状态机方法来解决。以下是对该问题的详细分析和优化方案。

动态规划方法

问题分析：小偷想要偷尽可能多的财富，但不能同时偷相邻的两个房子。我们可以用动态规划来解决这个问题。

状态定义：

• 设f[i]表示到第i个房子为止，小偷能偷到的最大财富值。
• 到第i-1个房子为止，他能偷的最大财富值为f[i-1]。

状态转移：

• 如果小偷不偷第i个房子，那么最大财富就是f[i-1]。
• 如果小偷偷第i个房子，那么他不能偷第i-1个房子，所以最大财富就是f[i-2] + h[i]（h[i]是第i个房子的财富值）。

初始条件：

• f[0] = h[0]（因为第一个房子可以偷）
• f[1] = max(h[0], h[1])（因为第二个房子可以和第一个房子同时偷吗？不行，所以只能偷其中一个）

优化空间复杂度：为了优化空间复杂度，我们可以使用滚动数组技术，只保留前两个状态的值。

状态机方法

问题分析：可以将问题建模为一个状态机，状态包括“最后一个房子选”和“最后一个房子不选”。

状态定义：

• v0：表示最后一个房子不选。
• v1：表示最后一个房子选。

状态转移：

• v0 → v0：如果不选当前房子，那么下一个房子可以选择选或不选。
• v0 → v1：如果不选当前房子，那么下一个房子可以选。
• v1 → v0：如果选了当前房子，那么下一个房子不能选。
• v1 → v1：如果选了当前房子，那么下一个房子也不能选。

初始条件：

• v0 = 0（初始时不选）
• v1 = h[0]（初始时选）

最终结果：max(v0, v1)

优化代码

动态规划优化代码：

public class Solution {    public int rob(int[] nums) {        if (nums == null || nums.length == 0) {            return 0;        }        int len = nums.length;        int[] dp = new int[len + 1];        dp[1] = nums[0];        for (int i = 1; i < len; i++) {            dp[i + 1] = Math.max(nums[i] + dp[i - 1], dp[i]);        }        return dp[len];    }}

空间优化代码：

public class Solution {    public int rob(int[] nums) {        if (nums == null || nums.length == 0) {            return 0;        }        int len = nums.length;        int[] dp = new int[3];        dp[1] = nums[0];        for (int i = 1; i < len; i++) {            int ind = (i + 1) % 3;            dp[ind] = Math.max(dp[ind + 1] + nums[i], dp[ind + 2]);        }        return dp[(len + 1) % 3];    }}

状态机优化代码：

public class Solution {    public int rob(int[] nums) {        if (nums == null || nums.length == 0) {            return 0;        }        int len = nums.length;        int[] dp = new int[2];        dp[0] = 0;        dp[1] = nums[0];        for (int i = 1; i < len; i++) {            int new0 = Math.max(dp[0], dp[1]);            int new1 = dp[0] + nums[i];            dp[0] = new0;            dp[1] = new1;        }        return Math.max(dp[0], dp[1]);    }}

测试示例

假设输入数组为：nums = [1, 2, 3, 4, 5]

动态规划计算过程：

• f[0] = 1
• f[1] = max(1, 2) = 2
• f[2] = max(2, 1 + 3) = max(2, 4) = 4
• f[3] = max(4, 2 + 4) = max(4, 6) = 6
• f[4] = max(6, 4 + 5) = max(6, 9) = 9

最终结果：9

状态机计算过程：

• v0 = 0, v1 = 1
• i=1: new0 = max(0,1)=1, new1=0+2=2 → v0=1, v1=2
• i=2: new0 = max(1,2)=2, new1=1+3=4 → v0=2, v1=4
• i=3: new0 = max(2,4)=4, new1=2+4=6 → v0=4, v1=6
• i=4: new0 = max(4,6)=6, new1=4+5=9 → v0=6, v1=9

最终结果：max(6,9) = 9

总结

该问题可以通过动态规划和状态机方法解决，动态规划方法直观且易于理解，状态机方法则提供了另一种建模思路。通过滚动数组优化，可以将空间复杂度从O(n)降低到O(1)，提高了内存效率。对于较大的输入规模，这种优化尤为重要。

转载地址：http://oqbs.baihongyu.com/