“This is my 38th day of participating in the First Challenge 2022. For details: First Challenge 2022”

I. Problem description

You are a professional thief, planning to rob the houses along the street. There is a certain amount of cash hidden in each room, and the only constraint on your ability to steal is that adjoining houses are equipped with interconnected security systems that will automatically alert the police if two houses are broken into on the same night.

Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount of money you can steal in one night without setting off the alarm.

Title link: Robbery

Two, the title requirements

Sample 1

Input: [1,2,3,1] Output: 4 Explanation: Steal House # 1 (amount = 1), then steal House # 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4Copy the code

The sample 2

Input: [2,7,9,3,1] Output: 12 Explanation: Steal House 1 (amount = 2), House 3 (amount = 9), then House 5 (amount = 1). Maximum amount stolen = 2 + 9 + 1 = 12.Copy the code

Data range

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

inspection

2. The recommended time is 5 to 15 minutesCopy the code

Third, problem analysis

This is also a typical dynamic programming problem, dynamic programming has not done can see this entry problem solution:

Day 34: Frog jumps step

Here’s our three-step routine:

Step 1: Understand what it means

First, the problem can be solved by dynamically programming a one-dimensional array, so what does dp[I] stand for?

So let’s see what they’re asking, the maximum amount of money that can be stolen without violating the alarm, so dp[I] is the maximum amount of money that can be stolen from up to the ith house.

Step 2 Variable initialization:

Dp [1]= Max (nums[0],nums[1]) dp[1]= Max (nums[0],nums[1])Copy the code

The third step:

So what’s the pattern? Let me show you example 2 in detail:

From the third number, dp[I] is satisfied

Dp [I] = Max (dp [I] – 2 + nums [I], dp [I – 1])

Three steps, call it a day!

Four, coding implementation

#include<iostream>
#include<algorithm>
using namespace std;
int main(a)
{
	int n,nums[105],i,dp[105];/ / initialization
	cin>>n;// The size of the input array,n is 0 or 1
	for(i=1; i<=n; i++)// Enter the elements of the array
		cin>>nums[i];
	dp[1]=nums[1],dp[2] =max(nums[1],nums[2]);// Initialize the first two digits of dynamic programming
	for(i=3; i<=n; i++)// The third digit starts the loop
	{
		dp[i]=max(dp[i- 1],nums[i]+dp[i2 -]);// Find the pattern
	}
	cout<<dp[n];// Output the result
	return 0;
}
Copy the code

V. Test results