392-打劫房屋

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

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

样例

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

挑战

O(n) 时间复杂度 且 O(1) 存储。

标签

爱彼迎 动态规划 领英

方法一（O(n) 时间复杂度 且 O(n) 存储）

使用动态规划，用一维数组 dp[i] 存储打劫第 i 所房屋时，最大收入。于是 dp[i] 的值仅仅和 dp[i -1]和 dp[i - 2] 有关，动态转移方程为

dp[i] = max(dp[i - 1], dp[i - 2] + A[i])

code

class Solution {

public:

    /*

     * @param : An array of non-negative integers

     * @return: The maximum amount of money you can rob tonight

     */

    long long houseRobber(vector<int> A) {

        // write your code here

        int size = A.size();

        if (size <= 0) {

            return 0;

        }

        if (size == 1) {

            return A[0];

        }

        vector<long long> dp(size, 0);

        dp[0] = A[0];

        dp[1] = max(A[0], A[1]);

        for (int i = 2; i < size; i++) {

            dp[i] = max(dp[i - 1], dp[i - 2] + A[i]);

        }

        return dp[size - 1];

    }

};

方法二（O(n) 时间复杂度 且 O(1) 存储）

优化 dp 数组，可以发现在计算 dp[i] 时，i - 2之前的元素完全用不上，所以可以用 3 个变量 dp_i 、dp_i_1 、dp_i_2 代替 dp[i] 、dp[i-1] 、dp[i-2]

code

class Solution {

public:

    /*

     * @param : An array of non-negative integers

     * @return: The maximum amount of money you can rob tonight

     */

    long long houseRobber(vector<int> A) {

        // write your code here

        int size = A.size();

        if (size <= 0) {

            return 0;

        }

        if (size == 1) {

            return A[0];

        }

        long long dp_i_1 = 0, dp_i_2 = 0, dp_i = 0;

        dp_i_2 = A[0];

        dp_i_1 = max(A[0], A[1]);

        for (int i = 2; i < size; i++) {

            dp_i = max(dp_i_1, dp_i_2 + A[i]);

            dp_i_2 = dp_i_1;

            dp_i_1 = dp_i;

        }

        return dp_i;

    }

};