如何一步步解决 DP 问题

转载自：https://leetcode.com/problems/house-robber/discuss/156523/From-good-to-great.-How-to-approach-most-of-DP-problems./177934

例题在这：Leetcode 198. House Robber

这类特定的问题可以用下面的顺序来处理：

1. 总结递归关系

2. 递归（自顶向下）

3. 递归 + 数组（自顶向下）

4. 迭代 + 数组（自底向上）

5. 迭代 + O(1) 变量（自底向上）

我们就按这个步骤一点一点改进我们的算法~

1. 总结递归关系

我们可以假设房子的编号从左到右递增，强盗当天晚上也是从左向右串门偷东西的。每走到一户人家，都可以选择：i）进去；ii）不进去。

i）进去抢第 i 个房子，将会获得这个房子里的财产数目，另外还应包括在进这个房子之前他的抢劫所得。由于不能抢相邻的房子，所以之前的抢劫所得就是前 i - 2 个房子的最大抢劫金额；

ii）不去抢第 i 个房子，强盗的所得没有增加，依然是前 i - 1 个房子的最大抢劫金额。

由上可得递归式：maxRob(i) = max( maxRob(i - 2) + nums[i], maxRob(i - 1) )。

2. 递归

把递归式转换成代码不是很难：

class Solution {
public:
    int robber(vector<int>& nums, int n) {
        if (n < 0) return 0;
        return max(robber(nums, n - 1), robber(nums, n - 2) + nums[n]);
    }

    int rob(vector<int>& nums) {
        return robber(nums, nums.size() - 1);
    }
};
/*
56 / 69 test cases passed.
Status: Time Limit Exceeded

Last executed input:
[114,117,207,117,235,82,90,67,143,146,53,108,200,91,80,223,58,170,110,236,81,90,222,160,165,195,187,199,114,235,197,187,69,129,64,214,228,78,188,67,205,94,205,169,241,202,144,240]
*/

这种方法简洁明了，但是却超时了。为什么会超时呢？因为 robber 这个函数同一个 n 值在递归过程中被计算了很多次。

3. 递归 + 数组

为了避免多次计算，我们可以把计算过的结果保存起来，因为 robber 的输入参数只有 n 是变化的，所以用个一维数组就 OK 了。

注意初始化 memo 的时候，如果默认初始化成 0，那么如果房子内物品的价值是 0 的时候，程序以为我们没保存这个数，就又会去算一遍，nums 数组中前面有很多连续 0 的话，一下就又 Runtime Error 了。废话说了很多，其实就是提醒自己，要把 memo 初始化成一个没意义的值（这里是 -1）：

class Solution {
public:
    int robber(vector<int>& nums, int n, vector<int>& memo) {
        if (n < 0) return 0;
        if (memo[n] != -1) return memo[n];
        memo[n] = max(robber(nums, n - 1, memo), robber(nums, n - 2, memo) + nums[n]);
        return memo[n];
    }

    int rob(vector<int>& nums) {
        int houseNum = nums.size();
        vector<int> memo(houseNum + 1, -1);
        return robber(nums, houseNum - 1, memo);
    }
};

这次没有超时了，但是递归仍然存在局限性，当递归的深度过深时，还是可能超时或栈溢出。

4. 迭代 + 数组

容易联想到，所有能用递归实现的，都可以改写成迭代的方法。

class Solution {
public:
    int rob(vector<int>& nums) {
        int houseNum = nums.size();
        if (houseNum == 0) return 0;
        vector<int> memo(houseNum + 1);
        memo[1] = nums[0];
        for (int i = 1; i < houseNum; ++i) {
            memo[i + 1] = max(memo[i], memo[i - 1] + nums[i]);
        }
        return memo[houseNum];
    }
};

这个改写也不难。两个数组同时出没，注意它们之间的序号对应关系。nums 有 houseNum 个元素，分别储存第 i 个房子的价值。memo 有 houseNum + 1 个元素，分别存储第 i 个房子及以前抢劫的最大值。

另外还要注意对于输入的判断，如果 nums 数组的长度是 0，直接对 memo[1] 赋值就报错了：

Runtime Error Message:
reference binding to null pointer of type 'value_type'
Last executed input:
[]

5. 迭代 + O(1) 变量

还有改进的空间吗？有！仔细观察就会发现，虽然每个 i 位置都需要计算一遍，但在计算时只依赖 i - 1 和 i - 2 这两个 memo 中的值。所以我们在迭代的时候把两个值更新一下就好了：

class Solution {
public:
    int rob(vector<int>& nums) {
        int houseNum = nums.size();
        if (houseNum == 0) return 0;
        int memo_0 = 0;
        int memo_1 = nums[0];
        for (int i = 1; i < houseNum; ++i) {
           int tmp = max(memo_1, memo_0 + nums[i]);
            memo_0 = memo_1;
            memo_1 = tmp;
        }
        return memo_1;
    }
};