LC.P198[打家劫舍]

方法一：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        f[1] = nums[0];
        for (int i = 2; i <= n; ++i) {
            // 1.不偷第 i 间房屋，总金额为 f[i - 1];
            // 2.偷第 i 间房屋，总金额为 f[i - 2] + nums[i - 1];
            f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]);
        }
        return f[n];
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：空间优化

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int rob(int[] nums) {
        int f0 = 0, f1 = 0;
        for (int i = 0; i < nums.length; ++i) {
            int newF = Math.max(f1, f0 + nums[i]);
            f0 = f1;
            f1 = newF;
        }
        return f1;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$