概览

同时洗劫了两家相邻的店铺时，会触发报警，问最多可以得到多少奖金

从前到后，线性DP.
每家有被偷和不被偷两种状态，状态机DP

题解

普通DP

f[i]: 抢劫前i家店铺的收益

状态计算
1. 抢劫第i家店铺 f[i-1]
2. 不抢第i家店铺 f[i-2] + w[i]

状态机

用到了第i-2层的状态，即用来两层的装填，现在的问题在于如果只有i-1层的状态解决这件事

把每个f[i]分解为两个状态：f[i][0], f[i][1];
0-选择了最后一个店铺
1-没有选择最后一个店铺

真的nb

每一步走一条边，其实就是将当前混沌的状态表示得很清晰明白，非常好的一件事。

0 –> 1

实际运行中，当前状态一定是由上一步的某个状态转移得到的，只要划分得细致。所以，感觉就是其实没有解决不了的问题。都能用动态规划来解决

状态1，每走一步表示走一个边；任何一个选择方案，都可以对应到一个长度为n的走法；同理，任何一个长度为n的走法，都可以对应到一个选择方案。

有些题可以降低维度

!!! 把一个过程用一个一个确定的过程和过程与过程之间的转移表示出来

f[i,j]: 所有走了i步，且当前处于状态j的所有走法的Max

f[i,0]:
- 从0 -> 0: f[i-1, 0]
- 从1 -> 0: f[i-1, 1]

f[i,1]:
- 只能从0到1: f[i-1, 0] + w[i];

代码

代码1

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n;
int f[N];

int main() {

    int T;
    scanf("%d", &T);
    while (T --) {
        scanf("%d", &n);

        f[0] = 0;
        for (int i = 1, w; i <= n; i ++) {
            scanf("%d", &w);
            f[i] = max(f[i - 1], f[max(0, i - 2)] + w);
        }

        printf("%d\n", f[n]);
    }
    return 0;
}

代码2

#include <iostream>
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int n;
int w[N], f[N][2];

int main() {

    int T;
    scanf("%d", &T);
    while (T --) {
        scanf("%d", &n);

        for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);

        f[0][0] = 0, f[0][1] = - INF;

        for (int i = 1; i <= n; i ++) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + w[i];
        }

        printf("%d\n", max(f[n][0], f[n][1]));
    }

    return 0;
}