LeetCode HOT100 - 打家劫舍

动态规划

子问题显然，因为每个数组当作是最后一个位置的话都是一个范围更小的子问题

每个位置只有打劫或不打劫两种

如果打劫的话，前面一家就不能打劫

所以每个位置都要维护 0/1 两种状态，方便后面转移

且 dp 的特点就在于当前最优，所以我们每次只需要从 i - 1 来转移就可以

class Solution {
public:
    int rob(vector<int>& a) {
        int n = a.size();
        vector<array<int, 2>> dp(n);
        dp[0][1] = a[0];
        dp[0][0] = 0;
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + a[i];
        }
        return max(dp.back()[0], dp.back()[1]);
    }
};