198. House raiding

Address ：

Power button https://leetcode-cn.com/problems/house-robber/ subject ：

You are a professional thief , Plan to steal houses along the street . There is a certain amount of cash in every room , The only restriction on your theft is that adjacent houses are equipped with interconnected anti-theft systems , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .

Given an array of non negative integers representing the storage amount of each house , Count you Without triggering the alarm , The maximum amount that can be stolen overnight .

Example 1：

Input ：[1,2,3,1] Output ：4 explain ： Steal 1 House No ( amount of money = 1) , And then steal 3 House No ( amount of money = 3).      Maximum amount stolen = 1 + 3 = 4 .

Example 2：

Input ：[2,7,9,3,1] Output ：12 explain ： Steal 1 House No ( amount of money = 2), Steal 3 House No ( amount of money = 9), Then steal 5 House No ( amount of money = 1).      Maximum amount stolen = 2 + 9 + 1 = 12 .

Tips ：

1 <= nums.length <= 100 0 <= nums[i] <= 400

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/house-robber
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

Adopt the idea of dynamic programming

Suppose the current house is i, that dp[i] Indicates the total amount of the stolen house

dp[i] Your choice depends on ：

        1. Current house selection ,i-1 You can't choose a house ,dp[i] = dp[i-2] + nums[i]

        2. The current house is not selected , It depends on dp[i-1] Value

Maximization is max(dp[i-1], dp[i-2] + nums[i])

Initial value ：

dp[0] = nums[0] No choice

dp[1] = max(nums[0], nums[1]) A choice

Method 1 、 Dynamic programming

      

#define max(a,b) ( (a) > (b) ? (a) : (b) )

int rob(int* nums, int numsSize){
	int i;
	int dp[101]={0};
	dp[0] = nums[0];

	for(i=1; i<numsSize; i++)
	{
		if(i == 1)
			dp[i] = max(nums[0], nums[1]);
		else
			dp[i]= max(dp[i-1], dp[i-2]+nums[i]);
	}
	
	return dp[numsSize - 1];
}

See more brush notes