[algorithm parsing leetcode by javascript] 213. robbery II

  javascript

clipboard.png

Title description

You are a professional thief. You plan to steal houses along the street. Each house has a certain amount of cash in it. All the houses in this place are in a circle, which means that the first house and the last house are next to each other. At the same time, adjacent houses are equipped with interconnected anti-theft systems. If thieves break into two adjacent houses at the same night, the system will automatically alarm.

Given a non-negative integer array representing the deposit amount of each house, calculate the maximum amount you can steal without touching the alarm device.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot steal house number 1 (amount = 2) and then house number 3 (amount = 2) because they are adjacent.
Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: You can steal house number 1 (amount = 1) and then house number 3 (amount = 3).
The highest amount stolen = 1+3 = 4.


analysis

This is a typical dynamic programming problem, but we need to consider several special situations.

This is called a ring, so both ends cannot be explored in parallel, so it is divided into two situations.

The first kind explores 0-(length-2)
The second exploration is 1-(length-1)

When considering only length 1 or 2

Comprehensive consideration

Release all code first

/**
 * @param {number[]} nums
 * @return {number}
 */
 var rob = function(nums) {
 //Special circumstances
 const len = nums.length
 if (len === 0) return 0
 if (len === 1) return nums[0]
 if (len === 2) return Math.max(nums[0], nums[1])
 
 const rob = function(nums, start, end) {
 let pMax = nums[start]
 let cMax = Math.max(pMax, nums[start + 1])
 
 for (let i = start + 2;   i <= end;  i++) {
 console.log(i,cMax,pMax)
 let tmp = cMax
 cMax = Math.max((pMax +nums[i]), cMax)
 pMax = tmp
 }
 
 return cMax
 }
 
 return Math.max(rob(nums, 0, len-2), rob(nums, 1, len-1))
 };

The dynamic programming function is rob

Rob under detailed analysis

Dynamic Planning Thought Based on Science Popularization

Dynamic programming is a branch of operations research and a mathematical method to solve the optimization of decision process. In the early 1950s, American mathematician R.E.Bellman and others proposed the famous principle of optimization when studying the optimization problem of multistep decision process. they transformed the multi-stage process into a series of single-stage problems and solved them one by one by using the relationship between the stages. they created a new method to solve the optimization problem of this kind of process-dynamic programming. In 1957, he published his famous work Dynamic Programming, which is the first book in this field.

In short, dynamic programming is to find the optimal solution for each stage.

Then let’s analyze according to the first case (from 0 to length-2)

Let’s assume that the array we are testing is
[3,1,5,12,6,8,13,2]
Then let’s explore
First, we explore the first two cases, and then we compare the two cases for each additional number to select the local optimal solution.
[3,1] The optimal solution is 3 before the optimal solution is 3
[3,1,5] The optimal solution is 3 [3+5] before 8
[3,1,5,12] the optimal solution is 3+12 = 15 > 8. the optimal solution is 8 before [3+12]
[3,1,5,12,6] the best solution is 15 > 8+6, the best solution is 15 before [3+12]
[3,1,5,12,6,8] the optimal solution is 15+8 > 15, the optimal solution is 15 before [3+12+8] is 23
[3,1,5,12,6,8,13] the optimal solution is 15+13 > 23. the optimal solution is 23 before [3+12+13]
[3,1,5,12,6,8,13,2] the optimal solution is 28 > 23+2 and the optimal solution is [3+12+13]

Analogy ensures that each stage has an optimal solution.

Final submission

clipboard.png

via