Foreword
The number tower problem is also known as the number triangle and number pyramid problem. The number tower problem is a common and important type of problem in multi-dimensional dynamic programming problems. It has many variants and the difficulty ranges from low to high. Mastering the algorithmic thinking of this type of problem is of great help in overcoming many multi-dimensional dynamic programming problems.
Of course, you may have discovered the blog I published before: Teach you to learn dynamic programming thoroughly – the digital triangle has been explained in detail in the introductory article. Of course, that article is very good, but because there are many variants of the digital triangle problem, then the blog I want to review the basic algorithm, so I record the digital triangle (explained in the morning and evening article) and extend the introduction to variant problems.
1. Prototype of a Number Tower Problem
1.1 Problem Description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
There is a number tower with multiple rows, and there are a number of numbers on the number tower. What is the maximum sum of the numbers passing through all the paths from the highest point to the bottom of the number tower?
As shown in the picture above, it is a 5-line number tower, in which the path of 7-3-8-7-5 passes through the number sum, which is 30.
1.2 Solution Ideas
Facing the number tower problem, using the greedy algorithm is obviously not feasible. For example, in the example given, if the greedy algorithm is used, the path chosen should be 7-8-1-7-5, and the sum of the numbers it passes is only 28, and Not the biggest. Using deep search DFS, it is easy to calculate that the time complexity is \(O(2^n)\) (because each number has two options: left and right). If the number of rows is too large, it will definitely time out.
Therefore, the number tower problem requires the use of dynamic programming algorithms.
①We can traverse from top to bottom.
It can be found that if you want to pass a number, you can only reach it from the number in the upper left corner or the upper right corner.
So obviously, when passing through any number A, the maximum sum of numbers passed by the path is the larger of the maximum sum of the numbers that can be achieved among the two numbers B at the upper left of the number A and the number C at the upper right. That one, plus that number A.
Therefore, the state transition equation is: $$dp[i][j] = max(dp[i – 1][j],d[i – 1][j – 1]) + num[i][j]$$
Among them, i, j represents the number of rows and columns, dp represents the maximum sum stored, and num represents the number at the position.
\(dp[i – 1][j]\) represents the upper left corner, \(dp[i – 1][j -1]\) represents the upper right corner.
Let’s illustrate with an example: when passing the number 1 in the third row, we first look at the maximum sum that can be achieved between the number 3 in the upper left corner and the number 8 in the upper right corner. 3 obviously has only one path 7-3, so the maximum sum is 10; 8 obviously has only one path 7-8, and its maximum sum is 15; the larger of the two is 15, so the maximum sum that can be achieved through 1 is 15+1=16.
In this way, we traverse step by step, and finally the maximum sum that can be achieved through each position is found. Just find the maximum value from the bottom row and output it.
②We can also traverse from bottom to top.
Whether a path goes from top to bottom or from bottom to top, the sum of the numbers it passes is the same, so this question can be turned into finding the maximum sum of numbers passed from the bottom to the highest point.
The writing method is the same as sequential traversal, except that when the state is transferred, max is taken from the lower left corner and lower right corner of the number. The advantage of writing reverse order traversal compared to sequential traversal is that it eliminates the last step of finding the max of the last row, and can directly output the value stored at the highest point.
1.3 Code Implementation
// Author: RioTian
// Time: 21/01/21
// #include <bits/stdc + + .h>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int dp[N][N], num[N][N];
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n;
cin >> n; //Input the number of rows in the tower
for (int i = 1; i <= n; + + i)
for (int j = 1; j <= i; + + j)
cin >> num[i][j]; //Input the data of the tower. Note that i and j should start from 1 to prevent the array from going out of bounds.
for (int i = 1; i <= n; + + i)
for (int j = 1; j <= i; + + j)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + num[i][j];
//The maximum sum of this number is the max in the upper left corner and the upper right corner, plus this number
int ans = 0;
for (int i = 1; i <= n; i + + )
ans = max(ans, dp[n][i]); //Find the maximum number from the last row
cout << ans << endl;
return 0;
}
2. Number Tower Problem Variant
2.1 Rectangular Number Tower
Take [Luogu P1508: Likecloud-Eat, eat, eat] as an example.
2.1.1 Problem Description
There is a numerical matrix with m rows and n columns (n is an odd number) (there are some negative numbers in the numbers).
Taking the bottom middle of the last row as the starting point, you can choose to move forward, left, or right for each move. Ask what is the maximum sum of numbers passed from the starting point to the other side of the matrix.
2.1.2 Sample
6 7
16 4 3 12 6 0 3
4 -5 6 7 0 0 2
6 0 -1 -2 3 6 8
5 3 4 0 0 -2 7
-1 7 4 0 7 -5 6
0 -1 3 4 12 4 2
S
As shown above, it is a numerical matrix with 6 rows and 7 columns. The starting point is ‘S’ below the number 4 in the last row. For the first move, you can choose to move to one of 3, 4, and 12 in the last row. If you choose to move to 4, you can choose to move to 4, 0, or 7 in the second row for the second move.
This matrix moves from the starting point to the other side of the matrix, and the maximum sum of numbers passed is 41.
2.1.3 Problem-solving ideas
Basically the same idea as the number tower problem.
However, when looping this question, you need to loop from the second row to the first row. (The last line has only three reachable points, so it can be skipped directly after initialization)
And there is one more option for state transition. The state transition equation is as follows:
\[dp[i][j] = max(dp[i + 1,j + 1],dp[i + 1,j – 1],dp[i + 1,j]) + num[i][ j] \]
Also note that there are negative numbers in the matrix, so the dp array needs to be initialized to a negative number with a large absolute value to prevent problems caused by accessing outside the matrix boundary during the transfer process. (Special processing can also be done at the boundaries of the matrix)
2.1.4 Code Implementation
// Author: RioTian
// Time: 21/01/21
#include <bits/stdc + + .h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
int dp[N][N], a[N][N];
int main() {
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, m;
while (cin >> m >> n) {
memset(dp, -9999, sizeof(dp)); //There is a pitfall. -9999 should be set here instead of -1
for (int i = 1; i <= m; + + i)
for (int j = 1; j <= n; + + j)
cin >> a[i][j];
dp[m][n / 2 + 1] = a[m][n / 2 + 1];
dp[m][n / 2] = a[m][n / 2];
dp[m][n / 2 + 2] = a[m][n / 2 + 2];
for (int i = m - 1; i > 0; --i)
for (int j = 1; j <= n; + + j)
dp[i][j] =
max(max(dp[i + 1][j + 1], dp[i + 1][j - 1]), dp[i + 1][j]) +
a[i][j];
int ans = 0;
for (int i = 1; i <= n; + + i)
ans = max(ans, dp[1][i]);
cout << ans << endl;
}
}
2.2 A number tower with time as a dimension
Take [HDU 1176 Free Pie] as an example.
This question has also appeared in KB’s DP series: KB question set
2.2.1 Problem Description
There is a 10-meter-long path. The starting point of the path is the origin of the x-axis, and the end point of the path is x=10. There are 11 coordinate points in total, x=0~10. (As shown below)
Each of the next n lines has two integers x and T, indicating that a pie will fall at the coordinate x at the T second.
Multiple pies may fall at the same point in the same second.
Initially, you are standing on x=5, you can move 1m per second, and you can catch pies at a point within 1m of your location at most.
For example, if you stand on x=5, you can catch all the pies on one of x=4, 5, and 6.
Ask how many pies you can receive at most.
2.2.2 Sample
6 (meaning there are 6 pies)
5 1 (at 1s, a pie falls on x=5)
4 1 (at 1s, a pie falls on x=4)
6 1
7 2 (At 2s, a pie falls on x=7)
7 2 (Multiple pies may fall at the same point in the same 1s)
8 3
In the example, up to 4 pies can be received.
One of the connecting methods is: catch a pie on x=5 in the 1st s, move to x=6 in the 2nd s, catch two pies on x=7, move to x=7 in the 3rd s, and catch x =8 for a pie, a total of 4 pies.
2.2.3 Problem-solving ideas
In essence, it is still a number tower problem, but now the dimension of “number of rows” becomes “time”.
To illustrate with an example: it can be understood that the numbers in columns 4, 5, and 6 of the first row are 1, the numbers in column 7 of the second row are 2, and the numbers in column 8 are 1. Then the starting point is row 0, column 5. Each time you move, you can choose three ways: downward, lower left, and lower right.
Therefore, the solutions are basically the same. Just pay attention to the additional conditions of the question when solving the problem.
2.2.4 Code Implementation
// Author: RioTian
// Time: 21/01/21
#include <bits/stdc + + .h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 50;
int dp[N][15], a[N][15];
int main() {
// freopen("in.txt", "r", stdin);
// ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n;
while (cin >> n & amp; & amp; n) {
int maxn = 0;
memset(dp, 0, sizeof dp), memset(a, 0, sizeof a);
int x, y, e = 0;
for (int i = 1; i <= n; + + i) {
cin >> x >> y;
a[y][ + + x] + + , e = max(e, y);
}
for (int i = e; i >= 0; --i)
for (int j = 1; j <= 11; + + j)
dp[i][j] =
max({dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]}) +
a[i][j];
cout << dp[0][6] << endl;
}
}
2.3 dual-threaded fetching (four-dimensional DP)
2.3.1 Example 1: [Luogu P1004: Taking numbers from squares]
2.3.1.1 Problem Description
There is an N×N grid map, put positive integers in some squares, and 0 in other squares.
Someone starts from the upper left corner of the grid chart and can only choose to walk down or to the right until he reaches the lower right corner. In the process, he can take away the number in the square (it becomes 0 after taking it). If you do this twice in a row, what is the maximum sum of the numbers taken out?
2.3.1.2 Sample
A
0 0 0 0 0 0 0 0
0 0 13 0 0 6 0 0
0 0 0 0 7 0 0 0
0 0 0 14 0 0 0 0
0 21 0 0 0 4 0 0
0 0 15 0 0 0 0 0
0 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0
B
As above, this is an 8×8 grid map. For the first time, 13, 14, and 4 are taken. For the second time, 21 and 15 are taken. The maximum sum is 67.
Note: The numbers in the square are given in the format of a b c, where a represents the number of rows, b represents the number of columns, and c represents the value.
For example, 2 3 13 means that the value of the second row and third column is 13.
2.3.1.3 Problem-solving ideas
If it is only a single thread, that is, it only goes once, then this question is no different from a rectangular number tower. Create a two-dimensional array \(dp[i,j]\) to store the data when walking to (i,j) The maximum sum is enough.
But this question is a double thread, so we need to create a four-dimensional array \(dp[i,j,k,l]\) to store the first time we go to (i,j), and the second time we go to (k ,l), the maximum sum obtained.
According to the meaning of the question, you can only go down or to the right when walking, so there are four situations to reach (i, j) and (k, l):
Go down for the first time, go down for the second time; –(i-1,j), (k-1,l)
Go down for the first time, go right for the second time; –(i-1,j), (k,l-1)
Go right for the first time, go down for the second time; –(i,j-1), (k-1,l)
Go right for the first time, go right for the second time; –(i,j-1), (k,l-1)
That is to say: the current state may originate from the transition of four previous states.
Therefore, the state transition equation is as follows:
\[dp[i,j,k,l] = max(dp[i – 1,j,k – 1,l],dp[i – 1,j,k,l – 1],dp[i, j – 1,k -1,l],dp[i,j-1,k,l-1]) \]
But you still need to pay attention! According to the meaning of the question, the number taken during the first move will become 0. If the second move passes through the same place, you can only get 0, so special judgment is required here:
if (i == k & amp; & amp; j == l) dp[i][j][k][l] -= num[i][j];
The meaning of the above code is that when you go to the same position twice, you can only take the value in the square once. Since it is taken twice in the state transition equation, you need to subtract it once in the special judgment here.
2.3.1.4 Code Implementation
// Author: RioTian
// Time: 21/01/21
#include <bits/stdc + + .h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 50;
int f[12][12][12][12], a[12][12], n, x, y, z;
int main() {
cin >> n >> x >> y >> z;
while (x != 0 || y != 0 || z != 0) {
a[x][y] = z;
cin >> x >> y >> z;
}
for (int i = 1; i <= n; i + + ) {
for (int j = 1; j <= n; j + + ) {
for (int k = 1; k <= n; k + + ) {
for (int l = 1; l <= n; l + + ) {
f[i][j][k][l] =
max(max(f[i - 1][j][k - 1][l], f[i - 1][j][k][l - 1]),
max(f[i][j - 1][k - 1][l], f[i][j - 1][k][l - 1])) +
a[i][j] + a[k][l];
if (i == k & amp; & amp; l == j)
f[i][j][k][l] -= a[i][j];
}
}
}
}
cout << f[n][n][n][n];
return 0;
}
2.3.2 Example 2: [Luogu P1006: passes a note]
2.3.2.1 Problem Description
There is a digital matrix with m rows and n columns. Find two non-repeating paths from the upper left corner to the lower right corner, and find the maximum value of the sum of the numbers taken twice.
Note: This question has one more requirement than 1 – the paths taken twice cannot be repeated, that is, \(i\ !=k,j\ !=l\)
Note 2: The values stored at the starting point and end point are both 0.
2.3.2.2 Problem-solving ideas
The specific idea is basically similar to the previous example, except that the additional requirements make the path non-repeatable, so we can no longer make special judgments like the above question, but we cannot allow the path to be repeated during the loop.
The method here is to let l start looping from j + 1 when writing the for statement.
Why does this avoid path duplication?
Because during the loop, l can never equal j, that is, it is impossible to reach the same coordinate when walking, which satisfies the meaning of the question.
2.3.2.3 Code Implementation
// Author: RioTian
// Time: 21/01/21
#include <bits/stdc + + .h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 50;
using namespace std;
int num[60][60];
int dp[60][60][60][60];
int main() {
int m, n;
while (scanf("%d%d", & amp;m, & amp;n) != EOF) {
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; i + + )
for (int j = 1; j <= n; j + + )
scanf("%d", & amp;num[i][j]); //Input matrix
for (int i = 1; i <= m; i + + )
for (int j = 1; j <= n; j + + )
for (int k = 1; k <= m; k + + )
for (int l = j + 1; l <= n; l + + ) //Let l start from j + 1
{
dp[i][j][k][l] = max(max(dp[i - 1][j][k - 1][l],
dp[i][j - 1][k][l - 1]),
max(dp[i - 1][j][k][l - 1],
dp[i][j - 1][k - 1][l])) +
num[i][j] + num[k][l];
} //Since the coordinates will not be repeated, no special judgment is needed.
printf("%d\\
",
dp[m][n - 1][m - 1][n]); //You need to pay attention to the value of the answer output at this time
//This is possible because the values stored in the end point and the starting point are both 0, otherwise the value of the end point needs to be added once.
}
return 0;
}
2.3.3 Spatial optimization of reducing four dimensions to three dimensions
In the above two examples, because four-dimensional arrays are opened, the space complexity is too large. Once the number of rows and columns is slightly larger, it may exceed the limited memory, so further optimization is needed to reduce the space complexity.
The idea of reducing four dimensions to three dimensions is as follows:
We can find that since only walking to the right or down is allowed during walking, either the number of rows or columns increases by one with each step.
Therefore, when the length of the two paths is the same (that is, when the number of steps taken is the same)\(i + j = k + l= number of steps + 2\)
Therefore, we can open a three-dimensional array \(dp[n + m – 2,x_1,x_2]\)
The first dimension represents the number of steps, and the number of matrix steps in m rows and n columns ranges from 0 to n + m-2.
The second and third dimensions represent the abscissa of the two paths respectively. As long as the number of steps and the abscissa are known, the ordinate can be calculated.
In this way, the space complexity is reduced.
Readers can try the code implementation by themselves.
2.3.4 Two-dimensional space optimization
Note: Before looking at the optimization of this step, it is recommended to study the knapsack problem section first.
When solving the knapsack problem, we used the method of rolling the array to reduce the array from two dimensions to one dimension. This is because in the knapsack problem, we only need to get the data of the previous “row”.
Similarly, in this question, since you can only go right or down, the state transition only requires the data of the previous row and column (that is, the previous step), so you can also use the rolling array to reduce the dimension to two dimensions.
2.3.4.1 Code Implementation
// Author: RioTian
// Time: 21/01/21
#include <bits/stdc + + .h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 50;
using namespace std;
int dp[200][200];
int num[200][200];
int main() {
int n, m;
scanf("%d%d", & amp;n, & amp;m);
for (int i = 1; i <= n; i + + )
for (int j = 1; j <= m; j + + )
scanf("%d", & amp;num[i][j]);
for (int k = 1; k <= n + m - 2; k + + ) //Number of steps, reducing this dimension by rolling the array
for (int i = n; i >= 1; i--) //The scrolling array needs to be processed in reverse order! ! !
for (int p = n; p > i; p--) // p>i is to prevent path duplication
{
dp[i][p] = max(max(dp[i][p], dp[i - 1][p - 1]),
max(dp[i - 1][p], dp[i][p - 1]));
dp[i][p] + = num[i][k - i] + num[p][k - p];
}
printf("%d\\
", dp[n - 1][n]);
return 0;
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 53123 people are learning the system