Thief theft problem
- 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 stored in each house, calculate the maximum amount you can steal without setting off the alarm.
Example 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 = 4.
Example 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.
- Do not steal from two neighboring houses, and try to steal as much as possible. This is a typical dynamic programming problem, and the idea is that since the maximum amount of money that can be stolen in the back room depends on the maximum amount of money that can be stolen in the front room, you can look backwards from the first house. Create an array dp where the NTH element stores the maximum amount of money that can be stolen from the first n houses:
- If there is only one house, then only this one can be stolen, then the maximum amount of money that can be stolen from the first 1 house is known and saved;
- If there are two houses, steal the most of them, then the maximum amount of money that can be stolen from the first two houses is known and saved;
- If there are 3 rooms, it can be divided into two situations: 1) stealing house 1 and 3; 2) Only steal houses. This can be abstracted into two subproblems, which are determined by whether the third house is stolen or not. Calculate the results of stealing (subproblem 1) and not stealing (subproblem 2) separately, and choose the largest. Now, the maximum amount of money that can be stolen from the first three rooms is known and saved for stealing the 4th, 5th… N house reference.
- If there are 4 rooms, then there are two situations: 1) steal 4 not steal 3; 4. These two cases are only related to the results of the amount stolen from the first three houses (DP [3]) and the amount stolen from the first two houses (DP [2]). Calculate the amount in these two cases and choose the largest, i.e
Max (Money for House 4 + DP [2], DP [3])
; - From this, it can be concluded that whether to steal or not to steal the NTH house only takes into account dp[n-1] and DP [n-2]+ the amount currently available in the DP array.
Max (dp[n-2] + thisValue, dp[n-1])
var rob = function(nums) {
// Check the exception
if(! nums || nums.length ===0) {return 0;
}
// Boundary conditions
if(nums.length < 3) {return Math.max(... nums); }Dp (I) = Max (dp(I -1), dp(2) + arr[I])
let dp = [];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(let i = 2; i < nums.length; i++){
dp[i] = Math.max(dp[i2 -] + nums[i], dp[i- 1]);
}
return dp[dp.length- 1];
};
Copy the code
To be continued…