Dry stuff: Graphical algorithms – Dynamic programming series
January 12, 2024
by Victor Henson
No Comments
Xiao Hao: I am a lion from The Center of Appropriate Science and Technology. I love algorithms and learning. I am not limited to boring programming codes, but I prefer to explain problems simply in a relaxed way.
Dynamic programming series 1: Climbing stairs
1.1 Concept Explanation
There are a lot of materials on dynamic programming. The official definition is to convert a multi-stage process into a series of single-stage problems, and solve them one by one by using the relationship between each stage. The relationship between the stages in the concept is actually referred to as the state transition equation. Many people find DP difficult (hereinafter referred to as DYNAMIC programming DP). The fundamental reason is that DP is different from some algorithms with fixed forms (such as DFS, dichotomy and KMP), and there is no actual step to specify what the first and second steps should do. Therefore, EXACTLY speaking, DP is actually an idea to solve problems.
The essence of this idea is that a large problem (one that can be represented by two or three parameters) can be solved by the results of several smaller problems (usually finding some special computational logic, such as maximizing).
So the general state transition equation that we see is basically this:
Opt: indicates a special calculation logic, usually Max or min.
I,j,k are all parameters that are used in defining the DP equation.
Each of these state transition equations, there are more or less subtle differences. This is actually very easy to understand, there are so many relations in the world, it is impossible to abstract out a completely applicable formula. So I personally don’t recommend memorizing various types of state transition equations. But is it true that the question type of DP is completely impossible to grasp and classify for analysis? I don’t think so. In this series, I’ll cover the topic of dynamic programming in a nutshell.
Let’s first look at the simplest DP problem to familiarize ourselves with the concept of DP:
Title: Suppose you are climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top? Note: given n is a positive integer.
Example 1:
Input: 2 Output: 2 Explanation: There are two ways to climb to the top of the building.
1 order plus 1 order
2 order
Example 2:
Input: 3 Output: 3 Explanation: There are three ways to climb to the top of the building.
1 order plus 1 order plus 1 order
1 order plus 2 order
2 order plus 1 order
1.2 Topic Diagram
Through analysis, we can make it clear that the problem can be decomposed into some subproblems containing optimal substructure, that is, its optimal solution can be effectively constructed from the optimal solution of the subproblem. The condition of “breaking a big problem into several smaller problems” ** is met. Therefore, we let dp[n] represent the total number of methods that can reach the NTH order, and the following state transition equation can be obtained:
dp[n]=dp[n-1]+dp[n-2]
Go up one step: There is one way.
Go up 2 steps: there are 1+1 and 2 ways.
Up 3 steps: The total number of ways to reach level 3 is the sum of the ways to reach level 1 and level 2.
So the total number of ways to get to order n is the sum of the ways to get to order N minus 1 and order N minus 2.
1.3 Go Language Example
According to the analysis, the code is as follows:
func climbStairs(n int) int {
if n == 1 {
return 1
}
dp := make([]int, n+1)
dp[1] = 1
dp[2] = 2
for i := 3; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
Copy the code
Dynamic programming series 2: maximum suborder sum
2.1 Maximum suborder sum
Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.
Example:
Input: [– 2, 1, 3, 4, 1, 2, 1, 5, 4].
Output: 6
Explanation: The maximum sum of continuous subarrays [4,-1,2,1] is 6.
Get the topic please do not see below the problem solution, first think by yourself 2-3 minutes….
2.2 Topic Diagram
First of all, a continuous subarray must end with a number, so we can define the state as follows:
Dp [I] : represents the maximum sum of a contiguous subarray ending with nums[I].
So why is it defined this way? Because that’s actually the easiest definition to think of! In the previous section, we mentioned that the state transition equation actually describes the relationship between small-scale and large-scale problems through 1-3 parameter equations.
Of course, if you don’t think about it, it’s perfectly normal! Because “the problem was first proposed in 1977, but the linear time optimal solution was not discovered until 1984.”
According to the definition of state, we continue the analysis:
If dp[I] is to be obtained, nums[I] must be selected. And the continuous subsequence represented by DP [I] and the continuous subsequence represented by DP [i-1] are likely to differ by only one nums[I]. namely
dp[i] = dp[i-1]+nums[i] , if (dp[i-1] >= 0)
But here we run into a problem. ** is likely to be itself a negative number. In this case, if dp[I] is derived from dp[I -1]+nums[I], then the result is actually smaller because dp[I] requires the maximum sum. ** So in this case, if dp[I -1]<0, then dp[I] is actually nums[I]. namely
dp[i] = nums[i] , if (dp[i-1] < 0)
To sum up, we can get:
Dp [I] = Max (nums [I], dp [I – 1) + nums [I])
The state transition equation is obtained, but we still need to deduce it through an existing state. We can think that **dp[0] must end with NUMs [0], ** so
dp[0] = nums[0]
In many cases, dp[I] ends up being the answer because dp[I] is itself defined as the problem in the question. But the definition of the state here, which is not the problem in the question, cannot directly return to the last state (this step often has beginners fall over). So the ultimate answer, in fact, is to look for:
max(dp[0], dp[1], … , d[i-1], dp[i])
After analysis, we drew a graph:
Assume that nums is [-2,1,-3,4,-1,2,1,-5,4]
2.3 Go Language Example
According to the analysis, the code is as follows:
func maxSubArray(nums []int) int {
if len(nums) < 1 {
return0} dp := make([]int, len(nums)) // make([]int, len(nums)) // dp[0] = nums[0]fori := 1; i < len(nums); I ++ {// handle dp[i-1] < 0if dp[i-1] < 0 {
dp[i] = nums[i]
} else {
dp[i] = dp[i-1] + nums[i]
}
}
result := -1 << 31
for _, k := range dp {
result = max(result, k)
}
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Copy the code
We can further simplify the code to:
func maxSubArray(nums []int) int {
if len(nums) < 1 {
return 0
}
dp := make([]int, len(nums))
result := nums[0]
dp[0] = nums[0]
for i := 1; i < len(nums); i++ {
dp[i] = max(dp[i-1]+nums[i], nums[i])
result = max(dp[i], result)
}
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Copy the code
Complexity analysis: Time complexity: O(N). Space complexity: O(N).
Dynamic programming series three: longest ascending subsequence
3.1 Longest ascending subsequence
Given an unordered array of integers, find the length of the longest ascending subsequence.
Example:
Input:,9,2,5,3,7,101,18 [10]
Output: 4
Explanation: the longest ascending subsequence is [2,3,7,101], which has a length of 4.
Note: There may be multiple combinations of the longest ascending subsequence, you just need to output the corresponding length.
C.
If you do not have ideas, please review the last learning content!
It is not recommended to read the problem directly!
3.2 Title Diagram
First of all, we analyze the topic, and we want to find the Longest Increasing Subsequence (LIS). Since continuity is not required in the problem, LIS may be continuous or discontinuous. At the same time, LIS meets the condition that it can be constructed from the optimal solution of its subproblem. So we can try to solve it with dynamic programming. First we define the state:
Dp [I] : represents the length of the longest ascending subsequence ending in nums[I]
We assume that nums is [1,9,5,9,3]
We will discuss it in two cases:
If nums[I] is smaller than all the preceding elements, then dp[I] is equal to 1 (itself).
If nums[I] is preceded by the element nums[j], then dp[I] is equal to dp[j]+1** (nums[3]>nums[0])
Let’s start with the above conclusions, but we find some problems. Because dp[I] does not have to have only one element before it!
May include nums[k], nums[p], and so on, in addition to NUMs [j]. So dp[I] could be dp[k]+1, dp[p]+1, etc., etc. So we need to find the maximum of dp[j]+1, dp[k]+1, dp[p]+1, and so on. (I made bold on 3, etc., etc., mainly because it’s very easy for beginners to fall over here! The purpose of emphasis here is to remember this question type!
That is:
Dp [j]+1, dp[k]+1, dp[p]+1,…..
Just meet:
nums[i] > nums[j]
nums[i] > nums[k]
nums[i] > nums[p]
.
In the end, we just need to find the maximum value in the dp array, which is what we’re looking for.
After analysis, we drew a graph:
3.3 Go language Example
According to the analysis, the code is as follows:
func lengthOfLIS(nums []int) int {
if len(nums) < 1 {
return 0
}
dp := make([]int, len(nums))
result := 1
for i := 0; i < len(nums); i++ {
dp[i] = 1
forj := 0; j < i; J++ {// this line of code is the one above, etc., etcif nums[j] < nums[i] {
dp[i] = max(dp[j]+1, dp[i])
}
}
result = max(result, dp[i])
}
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Copy the code
Dynamic programming series 4: triangle minimum path sum
In the previous chapter, we learned the analysis methods of DP (dynamic programming) in online relationships through the topics “longest ascending subsequence” and “maximum suborder sum”. This analysis method is also known as “linear dynamic programming” in operations research, which specifically refers to “linear functions with specific variables as the objective function, linear inequalities or equations of these variables as constraints, and the purpose is to find the maximum or minimum value of the objective function”. This point as we can understand, do not need to remember, not to copy!
In this section, we will continue to analyze a slightly different from the previous topic type, hope to be able to compare this topic with the previous topic demonstration, and then smooth solution!
4.1 Minimum path sum of triangles
Given a triangle, find the minimum sum of paths from top to bottom.
Example:
Each step can only move to the next node in the next row.
For example, given a triangle:
The minimum sum of paths from top to bottom is 11 (that is, 2 + 3 + 5 + 1 = 11).
4.2 Top-down graphical analysis
So first of all, we’re going to look for the sum of minimum paths of a triangle, what does that mean? Suppose we have a triangle: [[2], [3,4], [6,5,7], [4,1,8,3]]
So the minimum sum of paths from top to bottom is 2-3-5-1, which is 11.
Since we are using an array to define a triangle for our analysis, we change the triangle slightly:
So we’re stretching the whole triangle. In this case, according to the condition given in the problem: each step can only move to the next adjacent node in the next row. This is essentially the same thing as saying, for every step we can only move one down or one down to the right. To translate this into code, if 2 is at element position [0,0], then we can only move down to [1,0] or [1,1]. If 5 is in position [2,1], it can also move only to position [3,1] and [3,2]. As shown below:
Now that the problem is clear, let’s start the analysis. The problem is obviously one of finding the optimal solution, and can be constructed from the optimal solution of the subproblem. So we solve it by dynamic programming. First, we define the state:
Dp [I][j] : represents the minimum path sum of elements containing the ith row and j column
It’s easy to think of top-down analysis. And, whatever the final path is, it must go through the topmost element, which is [0,0]. So we need to initialize dp[0][0].
Dp [0][0] = the value of the element at position [0]
Further analysis, if we ask dp[I][j], then it must move from the two elements above its head.
The minimum path sum at 5, for example, is either 2-3-5 or 2-4-5. Then take the smaller of the sum of the two paths. Then we get the state transition equation:
However, we have a problem here! Except for the element at the top,
The element on the left can only come from above. (2-3-6-4)
The rightmost element can only come from its upper left corner. (2-4-7-3)
Then, we observe that the elements in line 2 are special elements (because they can only come from the element [0,0])
We can directly treat it specially and get:
dp[1][0] = triangle[1][0] + triangle[0][0]
dp[1][1] = triangle[1][1] + triangle[0][0]
In the end, we just have to find the smallest path sum in the last row, and that’s our answer. That is:
L: dp array length
Result = min(dp[l-1,0], dp[l-1,1], dp[l-1,1]….)
To sum up, we have finished the analysis. We have carried out 4 steps in total:
Define state
Summarize the state transition equation
Analyze the special case where the state transition equation cannot be satisfied.
Get the final solution
4.3 Code Analysis
After analysis, the code is self-contained:
func minimumTotal(triangle [][]int) int {
if len(triangle) < 1 {
return0}if len(triangle) == 1 {
return triangle[0][0]
}
dp := make([][]int, len(triangle))
for i, arr := range triangle {
dp[i] = make([]int, len(arr))
}
result := 1<<31 - 1
dp[0][0] = triangle[0][0]
dp[1][1] = triangle[1][1] + triangle[0][0]
dp[1][0] = triangle[1][0] + triangle[0][0]
for i := 2; i < len(triangle); i++ {
for j := 0; j < len(triangle[i]); j++ {
if j == 0 {
dp[i][j] = dp[i-1][j] + triangle[i][j]
} elseif j == (len(triangle[i]) - 1) {
dp[i][j] = dp[i-1][j-1] + triangle[i][j]
} else {
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
}
}
}
for _,k := range dp[len(dp)-1] {
result = min(result, k)
}
return result
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
Copy the code
Running the above code, we find that we are using too much memory. Is there any way we can compress memory? Observation shows that ** in our top-down process, we actually only need to use the data that has been accumulated in the previous layer, and do not revisit the previous element data. ** is drawn as follows:
The optimized code looks like this:
func minimumTotal(triangle [][]int) int {
l := len(triangle)
if l < 1 {
return0}if l == 1 {
return triangle[0][0]
}
result := 1<<31 - 1
triangle[0][0] = triangle[0][0]
triangle[1][1] = triangle[1][1] + triangle[0][0]
triangle[1][0] = triangle[1][0] + triangle[0][0]
for i := 2; i < l; i++ {
for j := 0; j < len(triangle[i]); j++ {
if j == 0 {
triangle[i][j] = triangle[i-1][j] + triangle[i][j]
} elseif j == (len(triangle[i]) - 1) {
triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]
} else {
triangle[i][j] = min(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j]
}
}
}
for _,k := range triangle[l-1] {
result = min(result, k)
}
return result
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
Copy the code
Dynamic programming series 5: minimum path sum
In the last section, we successfully solved the dynamic programming problem of “triangle minimum path sum” through analysis. In this section, we continue to look at a similar type of problem in order to fully grasp this “path sum” problem. Without further ado, let’s look at the title:
5.1 Minimum Path sum
Given an M x N grid of non-negative integers, find a path from the top left to the bottom right that minimizes the sum of the numbers along the path. Note: you can only move one step down or right at a time.
Example:
Input:
[
,3,1 [1].
,5,1 [1].
(4, 2, 1)
]
Output: 7
Explanation: Because path 1→3→1→1→1 has the smallest sum.
5.2 Graphic Analysis
First of all, let’s analyze the problem, and we want to find the minimum sum of paths, what does that mean? Suppose we have an m*n rectangle: [[1,3,1],[1,5,1],[4,2,1]]
So the sum of the smallest paths from the top left to the bottom right, which we can easily see is 1-3-1-1-1, this path, is equal to 7.
Now that the problem is clear, let’s move on. This problem is the same as the previous one to find the minimum path sum of a triangle. The problem obviously fits and can be constructed from the optimal solution of the subproblem, so we consider using dynamic programming to solve it. First, we define the state:
Dp [I][j] : represents the minimum path sum of elements containing the ith row and j column
Again, because any path to the lower right corner is going to go through the element [0,0]. So we need to initialize dp[0][0].
Dp [0][0] = the value of the element at position [0]
So if we want dp[I][j], it must be coming from above or to the left of itself. As shown below:
Five can only come from three or one
Two can only come from five or four
Four, moving from one
Three, moving from one
The red position must be moved from the blue position
The top line can only be moved from the left (1-3-1)
Leftmost column, which can only be moved from the top (1-1-4)
Finally, because our goal is to go from the top left to the bottom right, the minimum sum of the entire grid is actually the minimum sum of the paths that contain the elements in the bottom right. That is:
Let: the length of dp be L
Len (dp[L-1])-1
To sum up, we have finished the analysis. We have carried out 4 steps in total:
Define state
Summarize the state transition equation
Analyze the special case where the state transition equation cannot be satisfied.
Get the final solution
5.3 Code Analysis
After analysis, the code is self-contained:
func minPathSum(grid [][]int) int {
l := len(grid)
if l < 1 {
return 0
}
dp := make([][]int, l)
for i, arr := range grid {
dp[i] = make([]int, len(arr))
}
dp[0][0] = grid[0][0]
for i := 0; i < l; i++ {
for j := 0; j < len(grid[i]); j++ {
ifi == 0 && j ! = 0 { dp[i][j] = dp[i][j-1] + grid[i][j] }elseifj == 0 && i ! = 0 { dp[i][j] = dp[i-1][j] + grid[i][j] }elseifi ! = 0 && j ! = 0 { dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] } } }return dp[l-1][len(dp[l-1])-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
Copy the code
Again, running the above code, we find that we are using too much memory. Is there any way to compress memory? Through observation, we find that ** in the process of calculating the minimum path sum of each node from the upper left corner to the lower right corner, we only need to use the data that has been accumulated before, and ** will not access the previous element data again. (See if this process is similar to minesweeping. In fact, if you study the minesweeping plug-in, you will find that there is a similar analysis method in the core algorithm of minesweeping. I won’t go into the details here.)
The optimized code looks like this:
func minPathSum(grid [][]int) int {
l := len(grid)
if l < 1 {
return0}for i := 0; i < l; i++ {
for j := 0; j < len(grid[i]); j++ {
ifi == 0 && j ! = 0 { grid[i][j] = grid[i][j-1] + grid[i][j] }elseifj == 0 && i ! = 0 { grid[i][j] = grid[i-1][j] + grid[i][j] }elseifi ! = 0 && j ! = 0 { grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j] } } }return grid[l-1][len(grid[l-1])-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
Copy the code
Complex language features will not be used in any of the tutorials in this series, so don’t worry if you haven’t learned Go. Algorithmic thinking is the most important, and using GO is purely a hobby of the author.
The original article was first published in the public number – Hao Zai speak algorithm
