算法思路

该题就是一个简单的线性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];
    }
};