directory
1. What does dynamic programming give us as opposed to violent solutions? Why are there overlapping sub-problems and how can they be avoided? 2. Use examples of dynamic programming problems of different difficulties to illustrate, and finally review the three problems in the series of "House Robbery" again. Traditional recursion vs. DP 1. Solve recursion first 2. Step 1: Define the meaning of the DP array Step 2: Define the state transition equation Step 3: Initialize the initial value of the transition step 4: Optimizable point (optional) Case 1: Step 1: Define the meaning of dp array Step 2: Find the dynamic equation between the relational elements Step 3: Initialize the numerical setting Step 4: Optimization Case 2: Different paths "From Leetcode62" Step 1: Define the meaning of DP array Step 2: Step 3: Initialize the numerical setting Step 4: Optimization Case 3: Different paths II "From Leetcode63" Step 1: Define the meaning of the DP array Step 2: Find the dynamic equation between the relational elements Step 3: Initialize the numerical setting Step 4: Optimization Case 4: Step 1: Define the meaning of dp array Step 2: Find the dynamic equation between the relational elements Step 3: Initialize the setting Step 4: Optimization Case 5: Define the meaning of DP array Step 2: Finding dynamic equations between relational elements Step 3: Initialization SettingsCopy the codeDynamic programming – Hyperdetailed series
This article is longer and more detailed on the idea of dynamic programming, please be patient to follow the train of thought
Dynamic programming – Hyperdetailed series
Dynamic programming has always sounded like a very esoteric algorithmic idea. Especially in the first class of school algorithm, the teacher bala Bala listed a lot of algorithm core ideas, greedy, backtracking, dynamic planning… . “, began to feel that in the algorithm world with ease to solve all kinds of cattle B problems, did not think of or confused after learning is really learned (the university course is really a look). Later, I realized that college courses are generally entry-level explanations, which are used to expand horizons. If you really want to have your own opinions, you must work hard behind and form your own thinking logic.
Then back to the head, dynamic programming is still more difficult to understand, what overlap sub-problems, dynamic transfer equation, optimization point and so on, confused, finally think over the pain, take a good look at others to share understanding part of the problem, brush dozens of crazy. Basically, I can block and kill buddhas.
In the process of my learning and accumulation, I hope to sum up to give you a little help, I believe that after reading this article, you will feel the wonderful dynamic planning to you. We must also develop our own way of thinking about dynamic programming. Very 🐂 DP!!
First of all, outline what the article is going to talk about
1. What does dynamic programming bring us compared to violent solutions? Why are there overlapping sub-problems and how can they be avoided?
2. Use examples of dynamic programming problems of different difficulties to illustrate, and finally review the three problems in the series of “House Robbery” again.
After reading this article, I believe that you will have a preliminary thinking on THE DP problem, will certainly be a beginner. Later you can continue to practice related questions, practice makes perfect, thinking more will form their own thinking logic.
All right, let’s cut to the chase.
First, the advantages brought by dynamic programming
Very interesting, must see, there must be harvest, come on! 💪 💪 💪
Usually in the process of our algorithm design, the general concern is the implementation efficiency of the algorithm and the utilization of space efficiency
This is known as time complexity (the amount of time it takes to execute) and space complexity (the amount of memory it takes to execute)
The time complexity and space complexity are used to evaluate the efficiency of traditional algorithm design and dynamic programming
Traditional recursion vs. DP
First with a big guy for example to rotten 🌰, this chestnut is very rotten, but really very sweet: must emphasize emphatically.
“The NTH term of the Fibonacci sequence.”
** In my opinion, Fibonacci is an entry-level example of dynamic programming design, like “Hello World” in programming and “Word Count” in big data.
Fibonacci has almost perfectly illustrated the ideas and techniques that dynamic programming brings to the table without any other details to consider, and this is a very clear approach that seems to fit well with the whole dynamic programming way of thinking, the way of thinking about starting out.
Let’s look at the title first:
Write a function, input n, to find the NTH term of the Fibonacci sequence. The Fibonacci sequence is defined as follows: F(0) = 0, F(1) = 1 F(N) = F(n-1) + F(n-2), where N > 1. The Fibonacci sequence starts with 0 and 1, and the Fibonacci numbers that follow are the sum of the previous two numbers.Copy the codeCompare the traditional recursive solution with the dynamic programming solution
1. Recurse first
The traditional way of thinking about this kind of problem is to use recursion, which is relatively easy to do, is to keep recursively calling, see the following code:
class Solution(object) :
i = 0
def fib_recur(self, N) :
print "F(",self.i,") =", N # look only at N of the recursive output here
self.i += 1
if N <= 1:
return N
return self.fib_recur(N-1) + self.fib_recur(N-2) # Recursive output
Copy the codeOutput results:
F( 0 ) = 4
F( 1 ) = 3
F( 2 ) = 2
F( 3 ) = 1
F( 4 ) = 0
F( 5 ) = 1
F( 6 ) = 2
F( 7 ) = 1
F( 8 ) = 0
Copy the codeDouble counting
Clearly as you can see, a total of 8 times of calculation in the process, the same calculation results, the three of double-counting (the same color in the picture below, do not contain gray), that is to say, in the process of recursion, the calculated once again, the item of repeated computation, so for time efficiency is low, the only advantage is likely to be the code look more accessible, But it’s not a good algorithm design after all.
In this code, I’m going to recursively compute fib of N minus 1 plus FIB of N minus 2 when I compute N. So, in this case, I’m going to calculate fib of N minus 2. Would be one of the calculations in the figure below.
As you can see, there will be a considerable amount of double calculation, so that the time is repeated consumption.
Refer to items of the same color in the diagram, such as pink double-counting, yellow double-counting, etc
Note: there is no increase in space in the recursion, it is always the same length, just popping and pressing
In order to better illustrate the time efficiency caused by this kind of double calculation. For example, compared with the calculation node in the figure above, if another node is added and F(5) is added, more items (the part in the line box in the figure below) will be repeated due to the recursive calculation method. When calculating F(5), F(4) and F(3) will be recursively called. In the figure below, when calculating F(4), F(3) will be completely calculated. So, if N is large, there’s more time to consume.
In this way, the size of the tree is multiplied, and the time complexity is obviously multiplied. It’s scary in terms of time.
The inefficiency of time complexity greatly outweighs the readability of the code, so we can find a way to save the nodes that have been calculated in the past. In this way, we can use the time efficiency brought about by the idea of dynamic programming described below.
Time complexity: O(2N)O(2^N)O(2N) –> exponential
Space complexity: O(N)O(N)O(N)
2. Solve the problem in dynamic planning
To paraphrase the literal meaning:
Dynamic programming: we do not solve the problem directly, but at the time of solving the problem at each step, to achieve the optimal situation at each step. In other words, in the process of solving problems at each step, the past state and the current state are used to reach a current optimal state.
Planning: When solving this kind of problem, there will be a process of “filling in the form”. No matter it is one-dimensional form in simple case or two-dimensional form in complicated case, the idea of opening up space for time is to strive for the best time efficiency (the intermediate value of the process is saved for direct use later).
** Dynamic: ** Using the above example, each step in the recursive solution process is continuously solved “top down” from the basic problem, in each step, the same calculation logic is repeated. Compared with the recursive thought, the dynamic programming thought increases the preservation of the historical calculation results, gradually records the intermediate calculation results, and obtains the optimal value in each step.
Therefore, dynamic programming can avoid double calculation, achieve the optimal time, from O(2N)O(2^N)O(2N) exponential level to O(N)O(N)O(N) O(N) constant level, compared to open up a section of memory space to store the intermediate process value, is very worthwhile.
Then, let’s solve Fibonacci in accordance with the idea of dynamic programming
According to the rules in the question:
F(0) = 0, F(1) = 1
F(N) = F(N – 1) + F(N – 2), when N > 1
So, 👇👇F(N) is only related to its first two states 👇👇
A. Initialization value: F(0) = 0, F(1) = 1 b. F(2) = F(0) + F(1) –> save F(2) c. F(3) = F(2) + F(1) –> save F(3) d. If you want to calculate F(3), then F(4) = F(3) + F(2) –> save F(4).
Using the idea of dynamic programming, with a one-dimensional array assisted implementation of Fibonacci, see the following figure
Isn’t it a very simple idea, just by saving some values in the process can be very simple to use the loop, there is no need to use recursive repeated calculation to achieve.
What do you want to compute for the NTH value? So, here’s what we have to do
A. Define a one-dimensional array –> usually named dp
F(N) = F(n-1) + F(n-2)
C. Initialize values –> F(0) = 0 and F(1) = 1
Points A, B, and C above are the core elements of the dynamic programming idea
Let’s look at the code to implement (in this code, replace F() with dp).
class Solution(object) :
def fib(self, N) :
if N == 0:
return 0
dp = [0 for _ in range(N+1)] # 1 define dp[I] to hold the ith computed value
dp[0] = 0 # 2 Initialize
dp[1] = 1 # 2 Initialize
for i in range(2, N+1) :# 3 Dynamic equation implementation, since both 0 and 1 are assigned, we now need to assign from the second position
dp[i] = dp[i - 1] + dp[i - 2]
print dp # Record the number of times during the calculation, in contrast to the above recursion
return dp[N]
Copy the codeOutput:
[0.1.1.2.3]
3
Copy the codeAbove, the most important point is 1, 2, 3, and the execution process refers to the output compared to the recursive algorithm, calculation is much less, the same calculation is only calculated once.
Time complexity: O(N)O(N)O(N)
Space complexity: O(N)O(N)O(N)
With that said, let’s draw a dividing line for the above recursion vs. DP
Now that the dynamic programming scheme has also been introduced, let’s take a closer look to see whether there is room for optimization. After all, for the design of an algorithm scheme, the optimization point has to be found. Both the efficiency of time and space want to reach an ideal value.
3. Dynamic programming + optimization
If we look at this diagram, we see that each compute node is only related to the first two terms. In other words, we only need to save two values, and when evaluating the new node, assign the new value to the first of the first two values
So just two values, let’s define two variables dp1 and dp2. So, let’s simulate it step by step:
A. Initialization value: F(0) = 0, F(1) = 1
Incidentally, I assign F(1) to DP1 and F(2) to Dp2
C. F(3) = F(2) + F(1) –> save F(3)
Incidentally, I assign F(2) to DP1 and F(3) to Dp2
F(4) = F(3) + F(2) –> save F(4)
Incidentally, I assign F(3) to DP1 and F(4) to Dp2
So far, the whole process uses only two variables to store the values generated during the process, thus optimizing the spatial efficiency that was not optimized before
Let’s also paste the code for reference
class Solution(object) :
def fib_dp1(self, N) :
if N == 0: return 0
dp1, dp2 = 0.1
for i in range(2, N+1):
dp1 = dp1 + dp2
dp1, dp2 = dp2, dp1
return dp2
Copy the codeDoesn’t it look a little bit cleaner.
Yangzasa unconsciously wrote so much.
If some readers say that this is too easy, I am facing the content of this article is small white level, if the reader is medium up level, can directly skip to the following case three for reference.
In addition, if you have any opinion, please feel free to comment on my article, welcome & thank you for the discussion
How do you like this example? There are three points: 1. Define dp array 2. Initialization value
It is also why the Fibonacci sequence to the introduction of dynamic programming, because the Fibonacci sequence itself clear tell you what is dynamic equation, the value of the initialization, so thoroughly understand this kind of thought, especially from the traditional recursive – > dynamic programming ideas to solve, to optimize the aspect, is worth pondering.
Then, let’s find a few representative chestnuts to taste fresh
Is there a sense of dynamic programming at this point
This article is a long one, you can follow it or save it, you can also follow “computing advertising ecology”, reply to “DP” to get the PDF file of this article
Two, dynamic programming four steps to solve the problem
The Fibonacci sequence problem above leads to the following points, which are described in detail here
The following cases will try to strictly follow these steps to solve the problem
Step 1: Define the meaning of the DP array
Step 2: Define the state transition equation
Step 3: Initialize the initial value transferred by the process
Step 4: Optimizable points (optional)
Step 1: Define the meaning of the DP array
Most of the time, we’re going to define a one dimensional array or a two dimensional array to store the optimal value that we’re going to generate during the computation, and why is that optimal? Because in the process of solving the problem, the general dp array is used to store the optimal value from the beginning to the current situation, so the optimal value is saved so far, to avoid double calculation (for those who seem confused here, think about the comparison of Fibonacci recursive solution and dynamic programming above).
So, dp, whether it’s one-dimensional or two-dimensional, if you want to figure out what it represents, it generally represents the best value so far, right
Step 2: Define the state transition equation
What is the dynamic transfer equation? If there is a problem in front of us, then in the process of solving this problem, there will be a lot of overlapping sub-problems, overlapping sub-structures, and through the solution of these sub-problems, the problem will be finally solved
Generally speaking, in the process of problem solving, we can find a dynamic law that continuously solves sub-problems, such as F(N) = F(n-1) + F(n-2) in Fibonacci, while in other problems that can be solved by dynamic programming, we need to find such internal law by ourselves. This is the most difficult and final step, as long as this step is solved, then we basically have no problem solving this problem.
Step 3: Initialize the initial value transferred by the process
Following the idea of step 2, now that the dynamic equation has been defined, is it necessary to have a fulcrum to pry it for continuous calculation?
So, this fulcrum is going to be the initial definition, the activation of the dynamic equation, the calculation. For example, F(0) = 0 and F(1) = 1 in Fibonacci. With these two values, its dynamic equation F(N) = F(n-1) + F(n-2) can proceed
So that’s what we’re going to start with, but we’re going to have to figure it out.
Step 4: Optimizable points (optional)
The most important thing that can be optimized here is going to be the DP array, and there will be different problems and different optimization points
In this example, we will do different optimizations.
In a word, I suggest you write and draw as many pictures as possible. Many details will emerge.
Case 1: Robbery I “From Leetcode198”
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.Copy the codeExample 2:
Input:2.7.9.3.1] output:12Explanation: Stealing1House no. (Amount =2), and steal3House no. (Amount =9) and steal5House no. (Amount =1). Maximum amount stolen =2 + 9 + 1 = 12 。
Copy the codeLet’s discuss the classic case series separately. Let’s take a look at “Robbery I” first
The problem can solve with dynamic programming thought is that in the thief stealing in the process of continuously, always want to steal goods value maximum, the optimal, the stolen before each step and have a relationship, and want to consider whether can steal, every step will bring the biggest benefit, this makes we can use the ideas of the dynamic programming to solve the problem. Then strictly follow the four steps to solve the problem.
Step 1: Define the meaning of the DP array
As mentioned earlier, the value stored in the DP array generally represents the optimal value so far. In this problem, we define:
Dp [I] represents the maximum amount stolen at the ith house, which is the sum of the current maximum suborder
No matter how many houses there are, we finally take the last value of the DP array to get the maximum amount of money stolen by the thief
Step 2: Find the dynamic equation between the relational elements
The problem solved by dynamic programming, in general, is to solve the optimal sub-problem, “top down” to continuously calculate the optimal value of each step.
In order to obtain the value of dp[I], we must know dp[i-1], dp[i-2], dp[i-3]… The optimal value for each step of the transition, and in this transition, we have to figure out how to define the relationship. However, in the calculation of each step, there is a relationship with the previous several terms, and this fixed relationship is the overlapping subproblem we are looking for, which is also the dynamic equation to be defined in detail next
In this problem, when the thief reaches the ith house, he has two choices: one is to steal, the other is not to steal, and then chooses the one with the higher value
A. Calculation of stolen cases: dp[3] = NUMs [2] + DP [1], if the house is stolen, the neighboring house cannot be stolen, therefore, the general formula is: DP [I] = NUMs [i-1] + DP [i-2]
B. Calculation in case of no stealing: dp[3] = DP [2], if the house is not stolen, the adjacent house is its optimal value. Therefore, the general formula is: DP [I] = DP [i-1]
Finally, in order to steal the maximum amount, we must choose the maximum value between stealing and not stealing as the key point whether we choose or not. That is:
Dp [I] = Max (DP [i-1], NUMS [i-1]+ DP [i-2])
Step 3: Initialize the value Settings
When size=0, dp[0]=0; Dp [1]=nums[0]
So, here’s how to clean up the code:
class Solution(object) :
def rob(self, nums) :
# 1. Dp [I] represents the current maximum sum of suborders
Dp [I] = Max (dp[i-1], nums[i-1]+dp[i-2])
# 3. Initialize: give dp a position when there is no house, that is: dp[0]
# 3.1 Dp [0]=0 when size=0;
Dp [1]=nums[0]
size = len(nums)
if size == 0:
return 0
dp = [0 for _ in range(size+1)]
dp[0] = 0
dp[1] = nums[0]
for i in range(2, size+1):
dp[i] = max(dp[i-1], nums[i-1]+dp[i-2])
return dp[size]
Copy the codeTime complexity: O(N)
Space complexity: O(N)
So let’s think about what we can optimize to free up as much computer resources as possible
Step 4: Optimize
From the relationship between DP [I] = Max (DP [i-1], NUMS [i-1]+ DP [i-2]), each dynamic change is related to the previous two states (DP [i-1], DP [i-2]), and some of the previous values are not necessary to be retained.
So, dp only needs to define two variables to reduce the space complexity to O(1)
class Solution(object) :
def rob_o(self, nums) :
Dp [i-1] = dp[i-2] = dp[i-1] = dp[i-2
# Therefore, we can use two variables to hold the first two state values
O(N) -> O(1)
size = len(nums)
if size == 0:
return 0
dp1 = 0
dp2 = nums[0]
for i in range(2, size+1):
dp1 = max(dp2, nums[i-1]+dp1)
dp1, dp2 = dp2, dp1
return dp2
Copy the codeTime complexity: O(N)
Space complexity: O(1)
After finishing “I”, another topic was interspersed in the middle, a problem solved by using two-dimensional DP.
Finally, I said “Raiding house II” and “Raiding house III”, to figure out the problem of this series of raiding house, I believe you have a more profound entry experience of dynamic planning
If some readers say that this is too easy, I am facing the content of this article is small white level, if the reader is medium up level, can directly skip to the following case three for reference.
In addition, if you have any opinion, please feel free to comment on my article, welcome & thank you for the discussion
Case 2: Different paths “From LeetCode62”
A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below).
The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).
How many different paths are there?
Example 1:
Enter: m =3, n = 2Output:3Explanation: Starting at the top left corner, there are total3Path to the bottom right corner.1.Right -> right -> down2.Right -> down -> right3.Down -> right -> rightCopy the codeExample 2:
Enter: m =7, n = 3Output:28
Copy the codeTip:
1 <= m, n <= 100. The answer is guaranteed to be less than or equal to 2 times 10 to the ninth
Here are four steps to discuss:
Step 1: Define the meaning of the DP array
The current problem goes from the top left to the bottom right, and they say you can only go right or down, so we have to define a two-dimensional array to hold the value of the calculation. So, this definition:
Dp [I][j]: represents the total number of all paths to position (I, j)
That is, the sum of all paths of the robot from the upper left corner to the lower right corner, and the value of each position in DP represents the total number of paths to each position of (I, j)
Step 2: Find the dynamic equation between the relational elements
Because they say you can only go right or down, so when the robot moves, it can only go right or down.
So, in both cases, if you want to go to position (I, j), you can go from position (I -1, j) or from position (I, j-1). Therefore, the total number of paths to position (I, j) must be the number of paths to position (I -1, j) + the number of paths to position (I, j-1). So, we can now define the dynamic equation:
Dynamic equation: DP [I][J] = DP [i-1][J] + DP [I][J-1]
Step 3: Initialize the value Settings
Obviously, when the robot goes to row 0, column 0, no matter how it goes, there’s only one way to go.
Therefore, the initialization value must be set to either dp[0..m][1] or dp[1][0..n] equal to 1
So the initial values are as follows:
Dp [0] [0… n – 1) = 1; // The robot goes straight to the right, and all columns 0 are 1
Dp [0… m – 1] [0] = 1; // The robot goes all the way down, and the 0 column is all 1
Now, let’s clean up the code along these lines
class Solution(object) :
def uniquePaths1(self, m, n) :
Initialize the table, since row 0 and column 0 are initialized to 1. So let's set all of them to 1
dp = [[1 for _ in range(m)] for _ in range(n)]
for i in range(1, n):
for j in range(1, m):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[n-1][m-1]
Copy the codeSince either dp[0..m][1] or dp[1][0..n] is equal to 1, we assign an initial value of 1 to both of them when defining the two-dimensional array dp
Then calculate the total number of paths at each position, starting at position (1, 1)
Time complexity: O(M*N)
Space complexity: O(M*N)
Now that WE’re here, let’s think about what we can optimize
Step 4: Optimize
Can be in accordance with the previous solution of the idea, should also be able to carry out certain optimization from the space
Referring to the previous case, the previous definition is one-dimensional array DP, and the optimization point is that each step is only related to the previous two calculated values. Then the optimization point is dp[N] -> DP1 and DP2, and the spatial complexity changes from O(N) -> O(1). If it is a large-scale data calculation, the spatial efficiency is greatly improved.
Now the dynamic equation in this example is dp[I][j] = dp[i-1][j] + dp[I][J-1], and it is clear that the state values in each step are only related to the adjacent values on the left and the values above. Example (use 3*4 for convenience) :
In this complete picture description, the robot starts to move from the position (1, 1) in the upper left corner, and gradually advances in accordance with the dynamic equation at each step. It is obvious that the sum of paths obtained by the robot for each space of movement is only related to its upper and left values. That is, when the robot moves to row 2, row 0 is completely useless.
Therefore, this optimization point comes out. In the algorithm design, DP only defines the array of 2 rows and N columns, which saves the space overhead of M-2 rows. This code if you want to understand, please design it yourself, write it yourself will have a more profound understanding, and then emphasize: think more, form a subtle way of thinking.
After looking at this step, is it obvious that the optimization point, why does not give you the code above? Because I saw a point where it looked like I could continue to optimize, so I continued to work on space overhead.
** Guide: ** According to our optimization scheme above, it says that “when the robot moves to line 2, the data in line 0 is completely useless”. In fact, the current smart reader you think, look again, in the figure below (extracted from the above). In fact, not only is row 0 completely useless, but in row 2, when you move to position (I, j), you compute position (I, j), and then you don’t have any data for position (I minus 1, j). In other words, as we go, some of the data from the first row is no longer useful, it’s still taking up space
You must think more, understand more, draw more
Following this line of thought, let’s look at the steps below, and also draw the problem solving with a one-dimensional array, and draw the analogy for each step:
Here, sleepy students can draw a picture by themselves, understand, personal feeling is a very good expansion of thinking
Next, in accordance with this idea of code implementation, you will find that the code is very simple
class Solution(object) :
def uniquePaths2(self, m, n) :
if m > n:
m, n = n, m
dp = [1 for _ in range(m)]
for i in range(1, n):
for j in range(1, m):
dp[j] = dp[j] + dp[j-1]
return dp[m-1]
Copy the codeTime complexity: O(m* N)
Space complexity: O(min(m,n))
Is not from the aspect of thinking simple and clean a lot
After making clear of the above chestnut, we will carry out a simple difficulty increase in the above example, to put it bluntly, is to hit a few obstacles on the road
To see:
Case 3: Different Paths II “From Leetcode63”
A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below).
The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).
Now consider that there are obstacles in the grid. So how many different paths are there going to be from the top left to the bottom right?
Note: The values of m and n are less than 100.
Example 1:
Input: [[0.0.0],
[0.1.0],
[0.0.0] output:2Explanation: There is an obstacle in the middle of the 3x3 grid. It's going from the top left to the bottom right2Different paths:1.Right -> right -> down -> down2.Down -> down -> right -> rightCopy the codeLet’s take a look at the two key points in the problem: key point 1: you can only go right or down key point 2:1 with obstacles, 0 without obstacles
According to key points 1 and 2, the discussion continues in four steps:
Step 1: Define the meaning of the DP array
The DP array defined in this problem has the same meaning as the DP array defined in the previous example, but since you’ve already defined a obstacleGrid, you can use it directly without having to create extra space so you can use the obstacleGrid as a dynamic plan to store the optimal value during the calculation
Step 2: Find the dynamic equation between the relational elements
Refer to the preceding paragraph and specify the dynamic equation as follows: obstacleGrid[I][j] = obstacleGrid[i-1][j] + obstacleGrid[I][J-1] As the robot has obstacles during its movement, add some constraints A to the dynamic equation. If the current obstacleGrid[I][j] is 0. Then, directly calculate the calculation procedure under the dynamic equation b. If the current obstacleGrid[I][j] is not 0. So let’s just set that value to 0
Therefore, during the dynamic equation traversal, judge obstacleGrid[I][J] first, and then perform the calculation and execution of the dynamic equation
Step 3: Initialize the value Settings
Compared with the previous problem, it is similar that when the robot goes to row 0 and column 0, no matter how it goes, there is only one way to go. However, due to the obstacle, when it reaches the obstacle, it cannot go down behind it (the first row is used as an example in the figure below).
So, when we initialize row 0, column 0, everything behind obstacle 1 is unreachable. So, initialize the logical representation of rows and columns:
Reachability = state of previous position and reachability of this position to get to this position
This position can only be reached if the previous position is 1 (reachable, only 1 way) and the current position is 0 (no obstacles), and then set the position to 1 (reachable, only 1 way)
Line 0 initializes the expression
obstacleGrid[0][row] = int(obstacleGrid[0][row] == 0 and obstacleGrid[0][row-1] = =1)
# 0 column initialization expression:
obstacleGrid[clo][0] = int(obstacleGrid[clo][0] = =0 and obstacleGrid[clo-1] [0] = =1)
Copy the codeWith all of this in place, code along those lines
class Solution(object) :
def uniquePathsWithObstacles1(self, obstacleGrid) :
# row length
m = len(obstacleGrid)
n = len(obstacleGrid[0])
# if you are at position (0, 0), you can't go anywhere
if obstacleGrid[0] [0] = =1:
return 0
Otherwise, position (0, 0) can be reached
obstacleGrid[0] [0] = 1
Initialize column 0
for clo in range(1, m):
obstacleGrid[clo][0] = int(obstacleGrid[clo][0] = =0 and obstacleGrid[clo-1] [0] = =1)
Initialize line 0
for row in range(1, n):
obstacleGrid[0][row] = int(obstacleGrid[0][row] == 0 and obstacleGrid[0][row-1] = =1)
# Start at position (1, 1) according to the dynamic equation
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 0:
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
else:
obstacleGrid[i][j] = 0
return obstacleGrid[m-1][n-1]
Copy the codeTime complexity: O(MXN)
Space complexity: O(1)
Step 4: Optimize
I’m not going to talk about the optimization here, there’s basically no optimization point, because I’m going to open up memory space, and I’m going to optimize space, but I’m going to do it in a given array, right
With the foundation of these cases, let’s finish the discussion on the remaining two topics of the classic “House robbery” series, and then we hope to communicate with you in different ways and learn from each other
If the reader is tired, you can save it first, save it, and then come back again after digesting the previous content.
Case 4: Robbery II “From LeetCode213”
You are a professional thief, planning to rob the houses along the street, each with a certain amount of cash hidden inside. 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 an interconnected security system, if two adjacent houses are broken into on the same night, the system will automatically alarm.
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:2.3.2] output:3Explanation: You can't steal first1House no. (Amount =2) and steal3House no. (Amount =2), because they are adjacent.Copy the codeExample 2:
Input:1.2.3.1] output:4Explanation: You can steal first1House no. (Amount =1) and steal3House no. (Amount =3). Maximum amount stolen =1 + 3 = 4 。
Copy the codeDifferent from Raiding House I, the house of Raiding House I is linear, while the house of Raiding House II is circular, so there will be more points to consider. Because the first is connected, we can set it in the following three cases:
A. Don’t steal the tail
B. Steal the head, not the tail
C. No stealing in the first place obviously, c has too much loss and won’t get the highest amount, so choose A and B. So, the following is divided into two cases, calculate the two cases without the head and without the tail respectively to determine which way the thief stole the highest amount of money.
The following analysis is still carried out according to the previous four steps
Step 1: Define the meaning of the DP array
Dp [I] represents the same meaning as before. The value stored in the DP array generally represents the best value so far
Therefore, dp[I] represents the highest amount stolen at the ith house, which is the current maximum sum of suborders
But at the end we’re going to talk about the last digit of the DP array with no heads and no tails, and then we’re going to get the larger of them, which is the highest amount we’re going to get
##### Step 2: Find the dynamic equation between the relational elements
The dynamic equation can be referred to “House Robbery I”, which has a very detailed graphic process. The changes of the dynamic equation in this example are exactly the same as before:
dp[i] = max(dp[i-1], nums[i-1]+dp[i-2])
Step 3: Initialize Settings
Dp [0]=0; dp[0]=0; Dp [1]=nums[0]
Because the front of the room is connected, the calculation is directly divided into two cases. The first one skips the first room, the second one skips the second room, and you get two arrays. Finally, just compare the size of the last digit. Solve!
After step 3 of this example, interested students can write their own code, which is very similar to the code of “House Robbery I”. After I write the optimized code, it may be more clear how to write. Let’s go straight to step 4. With the above case, let’s go straight to the optimized solution:
Step 4: Optimize
Similarly, from the relationship between DP [I] = Max (DP [i-1], NUMS [i-1]+ DP [i-2]), each dynamic change is related to the previous two states (DP [i-1], DP [i-2]), and some of the previous values are not necessary to be retained. Just save two variables to hold the optimal value of the procedure.
There are detailed comments in the code:
class Solution(object) :
def rob(self, nums) :
The difference is that the house is surrounded by a ring
# Then, there are three obvious cases:
# 1. No stealing in the first place
# 2. Steal the head not the tail
# 3. Don't steal the tail
# Obviously, the first way has too much loss, so choose 2 and 3.
# Then, divide into two cases and calculate the two cases respectively to determine which is larger and which is smaller
# 1. Dp [I] represents the current maximum sum of suborders
# 2. Dynamic equation: dp [I] = Max (dp] [I - 1 and, nums [I - 1) + dp/I - 2)
# 3. Initialize: give dp a position when there is no house, that is: dp[0]
# 3.1 Dp [0]=0 when size=0;
Dp [1]=nums[0]
# Calculate according to the optimization scheme of Raid I
# numS processing, respectively cut out the head and tail of the substring
nums1 = nums[1:]
nums2 = nums[:-1]
size = len(nums)
if size == 0:
return 0
if size == 1:
return nums[0]
def handle(size, nums) :
dp1 = 0
dp2 = nums[0]
for i in range(2, size+1):
dp1 = max(dp2, nums[i-1]+dp1)
dp1, dp2 = dp2, dp1
return dp2
res1 = handle(size-1, nums1)
res2 = handle(size-1, nums2)
return max(res1, res2)
Copy the codeTime complexity: O(N)
Space complexity: O(1)
Even when you are a thief, you have to plan step by step to get the highest amount of money.
Case 5: house robbery III “from leetcode337”
After robbing a street and a circle of houses, the thieves found a new area to burgle. There is only one entrance to this area, which we call the Root. In addition to the root, each house has one and only one parent house attached to it. After some sleuthing, the clever thief realized that “all the houses in this place are arranged like a binary tree.” If two directly connected houses are robbed on the same night, the house will automatically alarm the police.
Calculate the maximum amount of money a thief could steal in one night without setting off the alarm.
Example 1:
Input:3.2.3,null,3,null,1]
3
/ \
2 3
\ \
3 1Output:7Explanation: The maximum amount a thief can steal in one night =3 + 3 + 1 = 7.
Copy the codeExample 2:
Input:3.4.5.1.3,null,1]
3
/ \
4 5
/ \ \
1 3 1Output:9Explanation: The maximum amount a thief can steal in one night =4 + 5 = 9.
Copy the codeThe title is very good, but will immediately give a person a thief is not good when the foot…
Without further ado, let’s talk about the title itself
The thief in “House Snatching” goes from linear to circular to rectangular? Is I think simple, directly dry to the tree, is not looking very sweet, and very want to, look down, research…
To put together some ideas and follow four steps:
1. Since the house is a tree, we can traverse the tree in the traditional way (front order, middle order, follow-up) 2. The simple idea is to traverse the tree from the bottom up to get the best loot value. 3. Obtain the optimal value of each node, and finally select the optimal result
Analysis is still carried out in three steps (no optimization points)
Step 1: Define the meaning of the DP array
Dp [I] represents the node with the most loot (received the most money)
Step 2: Find the dynamic equation between the relational elements
According to every node we go to, there will be two situations, that is, steal (1) and do not steal (0). Let’s discuss it separately:
A. Dp [0] is used to indicate that the node does not steal the most money so far, so it is ok whether the son node steals or not.
So: dp [0] = Max (left [0], left [1]) + Max (right [0], right [1])
B. Dp [1] is used to represent that the node has stolen the most money so far, so none of the sons can be stolen.
So: dp[1] = value + left[0] + right[0]
Is there anything I don’t understand? And then to explain:
Left [0] means do not steal the left child to get the highest amount
Left [1] stands for stealing left children to get the highest amount
Right [0] means don’t steal the right child to get the highest amount
Right [1] stands for stealing the right child to get the highest amount
If there is not quite understand the words, message or private letter I contact me, at any time to harass me ha
Step 3: Initialize Settings
In this example, the initialization is simple. If the current tree shape is empty, return dp[0, 0].
The complete code with the tree initialization code && a bunch of comments is posted below:
# Definition for a binary tree node.
class TreeNode(object) :
def __init__(self, x) :
self.val = x
self.left = None
self.right = None
class Solution() :
def rob(self, root) :
# description:
# 1. Since the house is a tree, we can traverse it the traditional way of traversing a tree (pre-order, mid-order, subsequent)
# 2. The simple idea is to traverse the tree from the bottom up to get the best loot value. You can use subsequent traversal
# 3. Obtain the optimal value of each node, and finally select the optimal result
# 1. Dp [I] represents the most money received at this node and below
# 2. Dynamic equation:
# 2.1 dp[0] represents that the node is not stolen to get the most money, then it is ok to steal the son node or not. dp[0] = max(left[0], left[1]) + max(right[0], right[1])
# 2.2 dp[1] represents that the node is stolen to get the most money, then the son nodes cannot be stolen. dp[1] = var + left[0] + right[0]
# 3. Initialize: if the current tree shape is empty, return dp[0, 0]
def postTrasval(root) :
dp = [0.0]
if not root:
return dp
left = postTrasval(root.left)
right = postTrasval(root.right)
dp[0] = max(left[0], left[1]) + max(right[0], right[1])
dp[1] = root.val + left[0] + right[0]
return dp
dp = postTrasval(root)
return max(dp[0], dp[1])
if __name__ == '__main__':
# initial tree structure
T = TreeNode(3)
T.left = TreeNode(2)
T.right = TreeNode(3)
T.left.right = TreeNode(3)
T.right.right = TreeNode(1)
# The solution to the Question
s = Solution()
print(s.rob(T))
Copy the codeSo that’s all I want to talk about
Thousands of words, I did not expect to write so much
I would like to emphasize that I can cover more than 80% of the questions about dynamic programming with my understanding of all these questions and my own additional practice. Most of them are questions with DP as one-dimensional array and two-dimensional array, and there are very few strange questions. Therefore, this paper will be “home robbery” classic case explained in detail once, there are different paths of the problem, is also a classic topic, and the classic topic must be very representative. There are many optimization directions, and this article only introduces spatial optimization, because this is the most common.
Finally, you must draw more pictures, think more, solve the meaning of the hundred edges (hundred edges are a little too many hahaha)
Also, more understanding of the four steps, come on!
Later there will be an opportunity to share other common algorithm ideas in detail
If you feel helpful, you might as well pay attention to, like, forward up oh!!