LeetCode 198. House Robber(DP)

题目

题意：给你一个数组表示一个街道，每个数字表示一个房子里有多少钱，你可以打劫获得这些钱，但是不能同时打劫相邻的房子，问你最多可以得到多少钱，

题解：动态规划，DP[i][0]表示第0个房子没有打劫，DP[i][1] 表示第1个房子打劫了。

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