题解 | 不相邻取数

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
    int n;  // n：房屋的数量
    cin >> n;  // 读取房屋数量
    vector<int> nums(n);  // nums[i]：第i间房屋的金额
    for(int i = 0; i < n; i++)
        cin >> nums[i];  // 读取每间房屋的金额

    // 定义dp数组：dp[i]表示偷窃到第i间房屋时的最大金额
    vector<int> dp(n, 0);
    
    // 边界条件1：只有1间房屋时，最大金额就是该房屋的金额
    dp[0] = nums[0];
    
    // 边界条件2：有2间房屋时，只能偷其中金额较大的那间
    if (n >= 2) {  // 补充n=1时的安全判断（原代码隐含n>=2，此处完善）
        dp[1] = max(nums[0], nums[1]);
    }

    // 从第3间房屋开始（i=2），按转移方程计算dp[i]
    for(int i = 2; i < n; i++) {
        // 选择1：不偷第i间房 → 最大金额 = dp[i-1]
        // 选择2：偷第i间房 → 最大金额 = dp[i-2] + nums[i]（因为不能偷i-1）
        // 取两种选择的最大值
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }

    // 最终结果：偷窃到最后一间房屋（n-1）时的最大金额
    cout << dp[n - 1] << endl;
    return 0;
}

• 状态 dp[i]：表示偷窃到第 i 间房屋时，能获得的最大金额。
• 转移方程：对于第 i 间房屋，有两种选择（偷或不偷）：不偷第 i 间房：最大金额 = 偷窃到第 i-1 间房的最大金额（dp[i-1]）。偷第 i 间房：最大金额 = 偷窃到第 i-2 间房的最大金额 + 第 i 间房的金额（dp[i-2] + nums[i]）。取两种选择的最大值，即 dp[i] = max(dp[i-1], dp[i-2] + nums[i])。