198.打家劫舍

题目：https://leetcode.cn/problems/house-robber

思路

首先使用回溯的思路，要求得一夜之间能偷窃得到的最高金额，也就是求——从前 i 个房间一直考虑到最后一个房间，能盗取的最高金额。那么对于考虑前 i 个房间的最高金额，等于前 i-1 个房间最高金额和前 i-2个房间+第 i 个房间金额的最大值。这可以用回溯来实现。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();

        auto dfs = [&](this auto&& dfs, int i) -> int {
            if (i < 0) return 0;
            return max(dfs(i - 1), dfs(i - 2) + nums[i]);
        };

        return dfs(n - 1);
    }
};

可以对已经计算过的 i 的结果进行保存

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> memo(n, -1);

        auto dfs = [&](this auto&& dfs, int i) -> int {
            if (i < 0) return 0;

            if (memo[i] != -1) {
                return memo[i];
            }

            return memo[i] = max(dfs(i - 1), dfs(i - 2) + nums[i]);
        };

        return dfs(n - 1);
    }
};

在过程中可以发现，在“递”的过程没有处理，在“归”的过程采取了最大值的策略，因此可以只要“归”的过程，方向由自顶向下改为自底向上。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 2);

        for (int i = 0; i < n; i++) {
            f[i + 2] = max(f[i + 1], f[i] + nums[i]);
        }

        return f[n + 1];
    }
};

又由于 f[i+2] 的状态只与 f[i+1] 和 f[i] 的状态有关，所以可以改为滚动数组来做

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        int f0 = 0;
        int f1 = 0;

        for (int i = 0; i < n; i++) {
            int new_f = max(f1, f0 + nums[i]);
            f0 = f1;
            f1 = new_f;
        }

        return f1;
    }
};