题目描述

偷钱and不能偷相邻两家店

通过条件可以知道，如果要偷取store[i]这家店，那么i之前的店，只可以偷取store[i-1]或者store[i-2]，或者更加之前的店面。

设f[i]表示，偷取i以及前面所有店的最大金额总数，
那么，f[i] = max(f[i], f[j])，0 <= j <= i+2

由于所有店面的金额都是大于0的，所以，不可能存在我拿了i-2却不拿i的情况，
由此可知，只要通过这两步就可以得到正确结果。
f[i] = max(f[i], f[i-2]);
f[i] = max(f[i], f[i-3]);
（为什么不用判断i-4？因为拿了i-4，我肯定也会拿i-2）

同理，最后的结果会在f[n-1]和f[n-2]取大

样例

输入：
10 7 6 14
输出：
24

算法1

(DP) $O(n)$

C++ 代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int s[N], f[N];

int main() {
    int T;
    cin >> T;
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &s[i]);
        memset(f, 0, sizeof f);
        f[0] = s[0];
        f[1] = s[1];
        f[2] = s[0] + s[2];
        for (int i = 3; i < n; i++) {
            f[i] = max(f[i], f[i - 2] + s[i]);
            f[i] = max(f[i], f[i - 3] + s[i]);
        }
        cout << max(f[n - 1], f[n - 2]) << endl;
    }
    return 0;
}