打劫房屋 · House Robber

［抄题］：

假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。

给定一个非负整数列表，表示每个房子中存放的钱，算一算，如果今晚去打劫，你最多可以得到多少钱 在不触动报警装置的情况下。

给定 [3, 8, 4], 返回 8.

[暴力解法]：

时间分析：

空间分析：把结果数组的值都mod2，结果数组的空间就节省为2了

［思维问题］：

［一句话思路］：

结果只和2种状态有关，因此结果f数组要成为滚动数组，mod2

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

前0个不包括第0个，前0个加了也没事，所以i应该从2开始。i = 1,i<=n时操作，序列型记住等号不能丢
前i -2个不包括第i -2个，所以应该再加第i - 1个

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

状态函数f和数组搞混了

［总结］：

偷东西第0位没有意义，所以还是类似“爬楼梯”的坐标型

［复杂度］：Time complexity: O(n) Space complexity: O(1)

空间节约成定值了

［英文数据结构或算法，为什么不用别的数据结构或算法］：

偷东西可以有“偷了前0家”的概念，所以是序列型。

走路没有“走了前0步”的概念，所以是坐标型。

［关键模板化代码］：

4步即可。

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

打劫房屋 II · House Robber II 循环时加一点限制条件

打劫房屋 III · House Robber III 二叉树

[代码风格] ：

数组取值题的corner case不是没有对象的null，而是判断数组长度为0时应该怎么取数，要理解

public class Solution {
    /*
     * @param A: An array of non-negative integers
     * @return: The maximum amount of money you can rob tonight
     */
    public int rob(int[] A) {
        //corner case
        int n = A.length;
        if (n == 0) {
            return 0;
        }
        //state
        int[] f = new int[2];
        //initialization
        f[0] = 0;
        f[1] = A[0];
        //function
        for (int i = 2; i <= n; i++) {
            f[i % 2] = Math.max(f[(i - 1) % 2], f[(i - 2) % 2] + A[i - 1]);
        }
        //answer
        return f[n % 2];
    }
}

View Code