LeetCode 198. 打家劫舍

算法思路

该题就是一个简单的线性DP求最值问题，不过需要注意的是，该题目中有要求所选择的两个位置不能相邻，所以在分析状态转移方程时和一般的线性DP有点不同。

状态表示：
f[i]表示从1走到i能得到的最高金额

状态转移

以最后一个点作为不同点进行划分：
1. 不选第i点，那么问题转化为从1 ~ i - 1能取得的最高金额，即f[i] = max(f[i], f[i - 1])
2. 如果选择第i个点，因为不能选择相邻的点，所以前面只能从1 ~ i - 2中选，因此表示为 f[i] = max(f[i], f[i - 2] + nums[i])
3. 需要注意的是，因为只有当i >= 2时f[i - 2]才会合法，但是当i < 2时依然可以做出选择2，此时f[i] = max(f[i], nums[i]), 根据观察，我们在代码中可以将选择1与该选择2的特殊情况进行合并，即写为为 f[i] = max(f[i - 1], nums[i])

C ++代码

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;

        int n = nums.size();
        vector<int> f(n, 0);
        f[0] = nums[0];

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

算法改进

其实上面的分类讨论比较繁琐，原因都在于边界情况的处理，其实解决这个问题的一个办法就是在初始化状态函数时可以多开一个，下标从1开始，这样就可以不用处理边界情况，代码也简短很多。

C ++代码

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;

        int n = nums.size();
        vector<int> f(n + 1, 0);
        f[1] = nums[0];

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

        return f[n];
    }
};

LeetCode 213. 打家劫舍 II

思路分析

该题相较于第一题其实就只多了一个条件，就是首尾不能同时选择，因此这里会分为三种情况：
1. 选头不选尾
2. 选尾不选头
3. 头尾都不选

根据下图可以清晰地看出，根据闫氏DP分析法则中的不重不漏原则，由于情况1和2已经把情况3包含其中，所以我们只需要对情况1和情况2进行分析即可。

我们的算法思路是分别从前往后和从后往前进行两次DP，区间分别为1 ~ n - 1 和 n ~ 2，接下来的思路就与LeetCode 198. 打家劫舍 一模一样啦

C++ 代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (nums.empty()) return 0;
        if (n == 1) return nums[0];

        vector<int> f(n + 1, 0), g(n + 1, 0);
        f[1] = nums[0];
        for (int i = 2; i <= n - 1; i ++)
            f[i] = max(f[i - 1], f[i - 2] + nums[i - 1]);

        g[n - 1] = nums[n - 1];
        for (int i = n - 2; i ; i --)
            g[i] = max(g[i + 1], g[i + 2] + nums[i]);

        return max(f[n -1], g[1]);
    }
};

LeetCode 337. 打家劫舍 III

算法思路

和上两题不同，该题的DP模型为树形DP，在树形DP中，常常会出现选择结点时父节点与子节点相互制约的情况，在此题中即为不可选择两个相邻节点，根据闫氏DP分析法，我们的分析思路如下：

状态表示：

f[i][0] 表示偷完以i为根的子树，且不选择结点i的所有方案
f[i][1] 表示偷完以i为根的子树，且选择结点i的所有方案

属性：方案中金额的最大值

状态转移：

如果该结点状态为f[i][1]，表示选择该结点，所以它的左右子节点的状态必须为f[i -> left][0] 和 f[i -> right][0]，且可以同时选择；
如果该结点状态为f[i][0]，则表示并不选择该点，而左右子节点的状态没有限制，所以为了使该状态达到最大值，需要使左右子节点的状态同时也取最大值

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<TreeNode*, unordered_map<int, int>> f; //第二维
    int rob(TreeNode* root) {
        dfs(root);
        return max(f[root][0], f[root][1]);
    }

    void dfs(TreeNode* root)
    {
        if (!root) return;

        dfs(root -> left);
        dfs(root -> right);

        f[root][0] = max(f[root -> left][0], f[root -> left][1]) + max(f[root -> right][0], f[root -> right][1]);
        f[root][1] = root -> val + f[root -> left][0] + f[root -> right][0];

    }
};