This is the second day of my participation in the August More Text Challenge.
Everybody is good! I’m Johngo!
I did not expect to have reached the second stage. The topic of “dynamic planning” is very difficult, and it is not easy to understand. At present, I have done half of the topic. This article is actually one THAT I wrote before, and I’m using it to polish it up.
“Dynamic programming” look at this article I… Promise!
Objective: to give xiaobai and students without a clear idea of a guide!
** By the end of this article, you will have achieved a qualitative improvement in the logic of most dynamic programming.
This article is a long one, so you are advised to bookmark it or download it directly from GitHub (github.com/xiaozhutec/…
So, let’s get started…
Zero, first impression
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 to broaden my horizon. If I really want to have my own opinions, I must work hard behind and form my own thinking logic. Tips: This logic must be documented. It is true and sometimes forgotten.
Then back to the head, dynamic programming is still difficult to understand, overlapping sub-problems, dynamic transfer equations, optimization points and so on, confused, finally think over the pain, take a good look at others to share understanding part of the problem, after the crazy brush dozens of questions. Now turn a head to look again, be basically can Buddha block to kill Buddha.
In my learning and accumulation process, part of the “dynamic programming” of the problem out. Hope to give you a little help, I believe that by the time you read this article, you will feel the magic of dynamic programming to you. We must also develop our own way of thinking about dynamic programming.
Believe me! This is not a difficult article to read!
I. Main points of this paper
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 difficulty levels, and finally, we will review the three problems in the “House Robbery” series again!
“Dynamic programming” thinking logic
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.
Second, advantages brought by dynamic programming
There will be harvest after watching, 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.
Introduction: Traditional recursion vs. dynamic programming
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. Recursive solution
This is probably the first classic example of recursion in our university.
So first try recursively. It’s easy to do, just keep calling recursively.
Look at the following code:
def fib(self, n) :
print('calculation F (% d)' % n)
if n < 2:
return n
return self.fib(n-1) + self.fib(n-2)
Copy the codeOutput results:
To calculate F (4) to calculate F (3) to calculate F (2) to calculate F (1) to calculate F (0) to calculate F (1) to calculate F (2) to calculate F (1) to calculate F (0)
Copy the codeOne phenomenon is obvious: double counting
A total of nine times in the process of calculation, 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 item was calculated for the repeated computation again, this time efficiency is relatively 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.
It can be found that there is a considerable amount of double calculation, which is a repeated resource consumption for both time and space.
Refer to items of the same color in the diagram, such as pink double-counting, yellow double-counting, etc
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, it’s going to take more time.
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” as described below.
Time complexity: O(2^N) –> exponential
Space complexity: O(N)
2. Dynamic planning solution
Let’s get to the point:
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.
So, how does the “dynamic programming” approach help Fibonacci to solve the problem
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. Want to calculate F(2)
So F(2) = F(0) + F(1) –> F(0), F(1)
C. Want to calculate F(3)
So F(3) = F(2) + F(1) –> F(1), F(2)
D. want to calculate F(4)
So F(4) = F(3) + F(2) –> F(2), F(3)
Using the idea of dynamic programming, with a one-dimensional array assisted implementation of Fibonacci, see the following figure
Combined with the previous recursive call, this solution is not very simple idea, just by saving some values in the process can be very simple to use the loop can be realized, 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
First, define a one-dimensional array –> usually named dp
F(N) = F(n-1) + F(n-2)
Initialize values –> F(0) = 0 and F(1) = 1
The above three points are the core elements of the idea of dynamic programming or the steps to solve the problem!
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 calculating the new node value, 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
F(2) = F(0) + F(1) –> save F(2)
Incidentally, I assign F(1) to DP1 and F(2) to Dp2Copy the code
C. F(3) = F(2) + F(1) –> save F(3)
Incidentally, I assign F(2) to DP1 and F(3) to Dp2Copy the code
F(4) = F(3) + F(2) –> save F(4)
Incidentally, I assign F(3) to DP1 and F(4) to Dp2Copy the code
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.
Think of recursion again, this is exciting!!
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 comments, please feel free to comment on my article, welcome & thank you for the discussion!
For easy viewing, GitHub has saved: github.com/xiaozhutec/…
How do you like this example? There are three points: 1. Define dp array 2. Initialize values. 4. Optimize items
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 try fresh, the following is an illustration of the case:
Three, use the four steps of dynamic programming to solve the problem
The Fibonacci sequence problem above leads to the following points, which are described in detail here.
In the following cases, the problem will be solved as strictly as possible:
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 in the case so far.
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 and 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, but the main optimization point is the spatial optimization.
In a word, I suggest you write and draw as many pictures as possible. Many details will emerge.
Let’s take a look at all of them in the order we set them up
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: in the following picture, 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
Initialization: give dp a position when there is no house, that is: dp[0]
1 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 there is any opinion can be at any time to my article comments, welcome to discuss together!
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] = 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 dp[0..m]\[1]
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 you walk along, some of the data at the beginning of line 1 becomes useless and still takes 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 begin to draw a picture, understand, personal feeling is a very good expansion of thinking! Interesting!
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 it a lot simpler and cleaner in terms of thinking?
Figure out the chestnuts above it, we will be above the example of a simple difficulty to increase, to put it bluntly, is on the road to hit a few blocks!
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 two key points:
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 question has the same meaning as the DP array defined in the previous example, but as the array obstacleGrid has been defined in this question, you can use it directly without opening up additional space.
Then, use the obstacleGrid as the optimal value for the stored computation in the dynamic plan.
Step 2: Find the dynamic equation between the relational elements
Refer to the preceding topic to specify the dynamic equation: obstacleGrid[I]\[j] = obstacleGrid[i-1]\[j] + obstacleGrid[I]\[J-1]
Since the robot has obstacles in the process of moving, some restrictions are added to the dynamic equation above
A. If the current obstacleGrid[I][j] is 0. So, let’s go straight to the dynamic equation
B. If the current obstacleGrid[I][j] is not set to 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
So similar to the last problem, when the robot goes to row 0, column 0, no matter how it goes, there’s only one way to go, right
But because there are obstacles, it is impossible to walk down behind the obstacles (the first line is used as an example 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
This part of the optimization is not to talk about, there is basically no optimization point, before all because of their own to open up memory space, through the optimization of space, and this problem is in the given array operation.
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.
Note the GitHub address again, which contains the address of the document: github.com/xiaozhutec/…
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. Never steal in the first place
Obviously, the loss of method C is too large to obtain the highest amount, so a and B are selected.
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
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 save, just save two variables to preserve the optimal value of the process.
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)
Let’s look at the following situation for thieves.
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 first!
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 (pre-order, mid-order, follow-up).
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
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.
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
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 far, that’s all I want to talk about!
Thousands of words, I did not expect to write so much!
Let me emphasize one point. After understanding all these questions and practicing them by myself, I am sure that I can cover more than 80% of the questions about dynamic programming. Basically, dp is a one-dimensional array and two-dimensional array, and there are 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,, we must draw more drawing more drawing, more thinking, the solution of the meaning of 100 edges from their own!!
Also, more understanding of the four steps, come on!