背包问题

可以看成背包问题

状态表示：f[i]表示从前i个店中打劫 的最大价值

状态转移：

• 不选当前店：f[i - 1]
• 选当前店，则只能选上上个店，即f[i - 2] + v[i]

状态转移方程：f[i] = max(f[i - 1], f[i - 2] + v[i])

$时间复杂度O(N),空间复杂度O(N)$

空间可以用变量优化到常数级别

参考文献

算法提高课

AC代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int f[N];
int T, n, v;

int main(){
    cin >> T;
    while (T --){
        cin >> n;
        for (int i = 1 ; i <= n ; i ++){
            cin >> v;
            if (i == 1) f[i] = v;
            else if (i == 2) f[i] = max(f[i - 1], v);
            else f[i] = max(f[i - 1], f[i - 2] + v);
        }
        cout << f[n] << endl;
    }
    return 0;
}

状态机模型

$时间复杂度O(N),空间复杂度O(N)$

空间可以用变量优化到常数级别

参考文献

算法提高课

AC代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int T, n, v;
int f[N][2];

int main(){
    cin >> T;
    while (T --){
        cin >> n;
        for (int i = 1 ; i <= n ; i ++){
            cin >> v;
            if (i == 1) f[1][0] = 0, f[1][1] = v;
            else {
                f[i][0] = max(f[i - 1][0], f[i - 1][1]);
                f[i][1] = f[i - 1][0] + v;
            }
        }
        cout << max(f[n][0], f[n][1]) << endl;
    }

    return 0;
}