打家劫舍题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

Test example

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

题目分析

该题目比较简单，因为是相邻的两个屋子不能进行偷盗，所以必须相隔一个或者两个才行，那么其实可以看作是分为基数与偶数来处理，主要的问题是当两个基数相加（或两个偶数相加）的和还是小于前面的一个基数（或偶数）下标的元素时如何判断，这里其实就可以直接判断想加完之后值的大小，直接取最大的替换该时候的值即可。

代码如下

C++

#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Solution {
public:
    int rob(vector<int>& nums) {
        int sobCar=0;
        int  sobVen=0;
        int lent=nums.size();
        for(int i=0;i<lent;i++){
            if(i%2==0){
              sobVen+=nums[i];
              sobVen = max(sobVen, sobCar);
            }else{
                sobCar+=nums[i];
               sobCar=max(sobVen, sobCar) ;
            }

        }
      //  cout<<sobCar<<"sadss"<<sobVen;
        return(max(sobCar,sobVen));
    }
};

int main(){
    vector<int>a(4,0);
    for(int j=0;j<a.size();j++){
        cin>>a[j];
    }
    Solution s;
    int endA=s.rob(a);
    cout<<endA<<endl;

}

python

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        dp = [0] * (n + 1)
        dp[1] = nums[0]
        for i in  range(2,n + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
        return dp[-1]