题意概括

你是一名专业小偷，计划偷窃一条街上的房屋。每间房屋内都存放着一定数额的现金。如果你在同一晚闯入两间 相邻 的房屋，防盗系统就会自动报警。给定一个代表每间房屋金额的非负整数数组，请计算在不触动警报的情况下，一夜之内能够偷窃到的最高金额。

数据范围:

• $1 \le n \le 100$ (房屋数量)
• $0 \le \text{nums}[i] \le 400$ (每间房屋的金额)

基础知识

这是一个经典的 动态规划 (Dynamic Programming) 问题。我们可以通过定义状态和状态转移方程来解决。

设 $dp[i]$ 为偷窃前 $i$ 间房屋（即数组中 nums[0] 到 nums[i-1]）所能获得的最大金额。当我们考虑第 $i$ 间房屋时（对应数组索引 i-1），我们面临两种选择：

1. 不偷第 $i$ 间房屋：如果我们决定不偷这间房，那么我们能获得的最大金额就等于偷窃前 $i-1$ 间房屋所能获得的最大金额。此时，收益为 $dp[i-1]$。

2. 偷第 $i$ 间房屋：如果我们决定偷这间房，根据规则，我们就不能偷它的邻居，即第 $i-1$ 间房屋。因此，总收益等于第 $i$ 间房屋的金额 nums[i-1] 加上偷窃前 $i-2$ 间房屋所能获得的最大金额。此时，收益为 $dp[i-2] + \text{nums}[i-1]$。

为了使收益最大化，我们在这两种选择中取较大者。因此，状态转移方程为：

空间优化： 我们注意到，计算 $dp[i]$ 只需要 $dp[i-1]$ 和 $dp[i-2]$ 的值。因此，我们不需要一个大小为 $N$ 的数组来存储所有中间状态，只需要两个变量来记录前两个状态即可，从而将空间复杂度从 $O(N)$ 优化到 $O(1)$。

该算法的时间复杂度为 $O(N)$，优化后空间复杂度为 $O(1)$。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

void run() {
    int n;
    cin >> n;

    int p2 = 0; // 相当于 dp[i-2]
    int p1 = 0; // 相当于 dp[i-1]

    for (int i = 0; i < n; ++i) {
        int m;
        cin >> m;

        // 计算 dp[i]
        int cur = max(p1, p2 + m);
        
        // 更新状态，为下一次迭代做准备
        p2 = p1;
        p1 = cur;
    }

    cout << p1 << endl;
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
4
1 2 3 1
输出:
4
(解释: 偷窃 1 号房屋 (金额 = 1) 和 3 号房屋 (金额 = 3)，总金额 = 1 + 3 = 4)

样例 2:
输入:
5
2 7 9 3 1
输出:
12
(解释: 偷窃 1 号房屋 (金额 = 2), 3 号房屋 (金额 = 9) 和 5 号房屋 (金额 = 1), 总金额 = 2 + 9 + 1 = 12)
*/