213. A house raid II
Answer:
-
On the basis of 213. Raiding II, this topic connects the houses at the beginning and the end together, thus producing two scenes:
- If you steal the first house, you can’t steal the last house, it’s the same as stealing from the first house to the last house.
- If you steal the last house, you can’t steal the first house, it’s the same as stealing from the second house to the last house.
So we can divide the house into two sections and then maximize the results together.
-
Analysis of state transition equation:
-
For house I, there are two scenarios, steal or not steal:
- If I don’t steal it,
dp[i] = dp[i - 1] + 0
- If stolen, then all the possible situation, before I was
dp[i] = Math.max(nums[i] + dp[i - 2], nums[i] + dp[i - 3], ...)
. So we know that each of these digits is taking the maximum possible value. So we can derive thisdp[i - 2] > dp[i - 3] > dp[i - 4]...
, sodp[i - 2]
The rest of the comparison can be omitted.
- If I don’t steal it,
-
State transition equation: dp[I] = math.max (dp[I] + 0, NUMs [I] + dp[I]).
-
/ * * *@param {number[]} nums
* @return {number}* /
var rob = function (nums) {
// Steal from 0 to nums.length-2 with dp1 recursion
// Since we are recursing two levels forward, two elements are created at one initialization, and both are maximized
let dp1 = [
// select * from user where id = 0
nums[0] | |0.// Only one of the first and the first households can be stolen
Math.max(nums[0] | |0, nums[1] | |0)];// Recurse from 1 to nums.length-2
for (let i = 2; i < nums.length - 1; i++) {
dp1[i] = Math.max(
// If you don't steal i-1, you only need to consider i-1
dp1[i - 1].// If you steal I, you need to consider i-2 to 0, and i-2 must be greater than all of the previous results
dp1[i - 2] + nums[i],
);
}
// Use dp2 recursion to steal from 1 to nums.length-1
// Since we are recursing two levels forward, two elements are created at one initialization, and both are maximized
Dp2 [0] stores 0 placeholders to ensure a one-to-one correspondence between dp2 index and NUMS
let dp2 = [
0.// I stole the first house
nums[1] | |0.// Only one of the first and second households can be stolen
Math.max(nums[1] | |0, nums[2] | |0)];// Recurse from 0 to nums.length-1
for (let i = 3; i < nums.length; i++) {
dp2[i] = Math.max(
// If you don't steal i-1, you only need to consider i-1
dp2[i - 1].// If you steal I, you need to consider i-2 to 0, and i-2 must be greater than all of the previous results
dp2[i - 2] + nums[i],
);
}
return Math.max(dp1[dp1.length - 1], dp2[dp2.length - 1]);
};
Copy the code