c++实现打家劫舍

以下是使用C++实现打家劫舍问题的代码：

#include <iostream>
#include <vector>
#include <algorithm>

int rob(std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return nums[0];
    } else if (n == 2) {
        return std::max(nums[0], nums[1]);
    }
    
    std::vector<int> dp(n, 0);
    dp[0] = nums[0];
    dp[1] = std::max(nums[0], nums[1]);
    
    for (int i = 2; i < n; i++) {
        dp[i] = std::max(nums[i] + dp[i-2], dp[i-1]);
    }
    
    return dp[n-1];
}

int main() {
    std::vector<int> nums = {2, 7, 9, 3, 1};
    std::cout << "Maximum amount that can be robbed: " << rob(nums) << std::endl;
    
    return 0;
}

该代码使用动态规划的思想解决打家劫舍问题。定义一个dp数组，其中dp[i]表示在第i个房屋时，能够获取的最大金额。根据题目要求，如果选择偷窃第i个房屋，则最大金额为第i个房屋的金额加上前两个房屋能够获取的最大金额，即nums[i] + dp[i-2]；如果选择不偷窃第i个房屋，则最大金额为前一个房屋能够获取的最大金额，即dp[i-1]。因此，dp[i]的值为这两种情况的较大值。最终，返回dp数组的最后一个元素即可得到最大金额