PROGRAMMING:Digital triangle
Look at the number pyramid below. Write a program to find the path from the highest point to the bottom of any end, so that the path through the number and the maximum. Each step can go from the current point to the lower left point or to the lower right point.
In the above example, paths from 13 to 8 to 26 to 15 to 24 produce the largest sum of 86.
###Input format:
The first row contains R (1 ≤ R ≤ 1000), indicating the number of rows.
The number of integers contained in a specific row of the pyramid.
All supplied integers are nonnegative and not greater than 100.
###Output format:
A single line containing the largest possible sum.
###Input example:
```in
five
thirteen
11 8
12 7 26
6 14 15 8
12 7 13 24 11
```
###Output example:
```out
eighty-six
```
answer：If there is no answer, please comment
[solution 1]
Triangle data storage generally uses two-dimensional array, as shown in the figure below.
This problem can be solved recursively. The basic idea is: D (I, J) represents the number J in the i-th line (I, J are calculated from 1), and maxsum (I, J) represents the sum of the numbers of the best path from the j-th number in the i-th line to the bottom. That is, to know the maximum value that can be reached at a certain point, we must know the maximum value that can be reached below or at the bottom right. Push to the bottom layer in turn to get the lowest value, and then calculate back to the vertex (1,1) in turn.
Starting from a certain D (I, J), it is obvious that the next step can only be d (I + 1, J) or D (I + 1, j + 1). If we take D (I + 1, J), then we get maxsum (I, J) is maxsum (I + 1, J) + D (I, J); If we take D (I + 1, j + 1), then we get maxsum (I, J) is maxsum (I + 1, j + 1) + D (I, J). So to choose where to go, we need to compare maxsum (I + L, J) and maxsum (I + 1, j + 1) which value is greater.
Reference code:
#include
#define MAX_ NUM 1000
int D[MAX_ NUM + 10][MAX_ NUM + 10];
int N;
Int maxsum (int i, int j) {/ / I is the row and j is the column
if (i == N) // End condition, if to the bottom, return its own value
return D[i][j];
int sum1 = MaxSum(i + 1, j); // If you want to know the maximum value of (I, J) from the left, you must first find the maximum value of the next layer
int sum2 = MaxSum(i + 1, j + 1);// Go down from the right
if (sum1 > sum2)
return sum1 + D[i][j];
return sum2 + D[i][j];
}
int main() {
int i, j;
scanf("%d", &N);
for (i = 1; i <= N; ++ i)
for (j = 1; j <= i; ++ j)
scanf("%d", &D[i][j]);
printf("%d\n", MaxSum(1, 1));
return 0;
}
[solution 2]: memory search
The program above is very inefficient. When n is not large, for example, when n = 100, it is almost impossible to work out the result. Why? It's because of too much double counting. A call to the maxsum (I, J) function may be called "a calculation.". Then, when calculating maxsum (I, J), maxsum (I + 1, J) should be calculated once, and when calculating maxsum (I, J-1), maxsmn (I + 1, J) should also be calculated once, so repeated calculation will occur. For the example given in the title, if the number of times maxsum (I, J) is calculated is written in position (I, J), then the following triangle can be obtained:
one
one one
one two one
one three three one
one four six four one
From the triangle above, This is the coefficient of the binomial, which is Yang Hui's triangle. As you can see, the total number of calculations in the last line is 16, and the total number of calculations in the penultimate line is 8. According to this rule, the complexity of the whole program is O (2n). That is, for n-line triangles, the total number of calculations is 20 + 21 + 22 +... + 2N-1 = 2N-1. When n = 100, 2n is a very large number, no computer can use this program to calculate the result in a person's lifetime.
Since the problem lies in repeated calculation, the only solution is to record a value once it is calculated, so as to avoid unnecessary repeated calculation. That is to say, when calculating the value of maxsum (I, J) for the first time, the value will be stored. When calculating maxsum (I, J) for the next time, you can directly take out the saved value without calling maxsum (I, J) again for recursive calculation. In this way, each maxsmn (I, J) only needs to be calculated once, then the total number of calculations (that is, the number of times to call the maxsum (I, J) function) is the total number of numbers in the triangle, that is, 1 + 2 + 3 +... + n = n ×( N + 1)/2。 The first line has one number, the second line has two numbers,..., and the nth line has n numbers.
How to store the calculated maxsum (I, J) value? It can be solved by using a two-dimensional array did [n] [n]: did [i] [J] stores the calculation results of maxsum (I, J). Next time you need the value of maxsum (I, J), you don't need to call maxsum (I, J) function, just take the value of did [i] [J]. This method is called mnemonic search.
Before giving the code of this method, we use the solution of Fibonacci sequence as an example to illustrate the application of memory search. The following recursive solution to the n-th term of Fibonacci sequence adopts the memory search method.
Code 1: Fibonacci sequence (traditional recursive method)
int fib(int n) {
if (n == 1 || n == 2)
return 1;
return fib(n - 1) + fib(n - 2);
}
The above code runs very slowly when n ≥ 40 and is easy to timeout. It must be optimized as follows:
Code 2: Fibonacci sequence (using memory search)
#include
int arr[47]; // Store intermediate calculation results: global variables, whose initial values are all 0
int fib(int n) {
if (n == 1 || n == 2)
return 1;
if (arr[n] != 0) // If the previous n-th item has been calculated
return arr[n]; // Return the nth item directly
/*
*If the nth item has not been calculated before, the nth item is calculated and the result is stored in the array
*/
return arr[n] = fib(n - 1) + fib(n - 2);
}
int main(void) {
int n;
while (scanf("%d", &n) != EOF) {
printf("%d\n", fib(n));
}
return 0;
}
With the basis of memory search, the reference code for finding the sum of number triangles is given as follows:
#include
#include
#define MAX_ NUM 1000
int D[MAX_ NUM + 10][MAX_ NUM + 10];
int N;
int did[MAX_ NUM + 10][MAX_ NUM + 10]; /* Store intermediate calculation results*/
/*Mnemonic search*/
Int maxsum (int i, int j) {/ * I is the row and j is the column*/
If (I = = n) / * end condition, if it reaches the lowest level, return its own value*/
return D[i][j];
If (did [i + 1] [J] = = 0) / * if maxsum (I + 1, J) has not been calculated*/
did[i + 1][j] = MaxSum(i + 1, j); /* If you want to know the maximum value of (I, J) from the left, you must first find the maximum value of the next layer*/
If (did [i + 1] [J + 1] = = 0) / * if maxsum (I + 1, j + 1) has not been calculated*/
did[i + 1][j + 1] = MaxSum(i + 1, j + 1); /* Go down from the right*/
if (did[i + 1][j] > did[i + 1][j + 1])
return did[i + 1][j] + D[i][j];
return did[i + 1][j + 1] + D[i][j];
}
int main() {
int i, j;
scanf("%d", &N);
/*Setting did to 0 means that all maxsum (I, J) have not been calculated at the beginning*/
memset(did, 0, sizeof(did));
for (i = 1; i <= N; ++ i)
for (j = 1; j <= i; ++ j)
scanf("%d", &D[i][j]);
printf("%d\n", MaxSum(1, 1));
return 0;
}
In the above program, the value of the elements of the did array is only calculated once, and the time taken to calculate once is constant, so the time complexity is O (N2), which is obviously much smaller than o (2n). Even if n = 1000, N2 is only 106. Data of this magnitude is more than enough in one second, and there is no TLE.
[solution 3]
The method of decomposing a problem into subproblems to solve recursively and saving the intermediate results to avoid repeated calculation can be called "dynamic programming". Dynamic programming is usually used to find the optimal solution. The problem of finding the optimal solution that can be solved by dynamic programming must satisfy that every local solution of the optimal solution is also optimal. Taking the above question as an example, each number in the best path to the bottom is the best path from the number to the bottom.
In fact, the idea of recursion does not need to be implemented as a recursive function in programming. In the example above, there is a recurrence formula
D(i,j) , i = N
MaxSum(i,j) =
Max {maxsum (I + 1, J), maxsum (I + 1, j + 1)} + D (I, J), others
It is not necessary to write a recursive function, starting from the element of the last line, it can get the final value of DP [1] [1]. The procedure is as follows:
#include
#include
#define MAX_ NUM 1000
int D[MAX_ NUM + 10][MAX_ NUM + 10]; /* Store digital triangles*/
int N; /* The number of rows of the number triangle*/
int dp[MAX_ NUM + 10][MAX_ NUM + 10]; /* State array*/
int max(int x, int y) {
return x > y ? x : y;
}
int main() {
int i, j;
scanf("%d", &N);
memset(dp, 0, sizeof(dp));/* The state array is all initialized to 0*/
for (i = 1; i <= N; ++ i)
for (j = 1; j <= i; ++ j)
scanf("%d", &D[i][j]); /* Input digital triangle*/
for (j = 1; j <= N; J + +) {/ * process the bottom line*/
dp[N][j] = D[N][j]; /* The value of the bottom row status array is the number itself*/
}
for (i = N - 1; i >= 1; I --) {/ * from the bottom to the top*/
for (j = 1; j <= i; j++) {
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + D[i][j];
}
}
printf("%d\n", dp[1][1]); /* The vertex (1,1) is the maximum value * / s
return 0;
}
As shown in the figure below, the number in the box is the maximum value that can be obtained.
I believe that after reading this diagram, it is not difficult for us to understand dynamic programming.
In fact, because the value of DP [i] [J] is useless after it is used to calculate DP [I - 1] [J], the calculated value of DP [I - 1] [J] can be directly stored in the position of DP [i] [J]. In this way, the calculated DP [n - 1] [1] replaces the original DP [n] [1], the calculated DP [n - 1] [2] replaces the original DP [n] [2]... The calculated DP [n-1] [n-1] replaces the original DP [n] [n-1]. In fact, the DP array only uses the last line to store all the results that should have been stored in the DP [n-1] line in the above program. In the same way, the DP array can store all the intermediate calculation results in the last row, and the final result (which should be DP [l] [l]) can also be stored in DP [n] [1]. Therefore, in fact, DP does not need to be a two-dimensional array, one-dimensional array is enough.
The rewritten procedure is as follows:
#include
#include
#define MAX_ NUM 1000
int D[MAX_ NUM + 10][MAX_ NUM + 10]; /* Store digital triangles*/
int N; /* The number of rows of the number triangle*/
int *dp; /* State array*/
int max(int x, int y) {
return x > y ? x : y;
}
int main() {
int i, j;
scanf("%d", &N);
for (i = 1; i <= N; ++ i)
for (j = 1; j <= i; ++ j)
scanf("%d", &D[i][j]); /* Input digital triangle*/
dp = D[N]; /* DP points to line n*/
for (i = N - 1; i >= 1; I --) {/ * from the bottom to the top*/
for (j = 1; j <= i; j++) {
dp[j] = max(dp[j], dp[j + 1]) + D[i][j];
}
}
printf("%d\n", dp[1]); /* （ 1,1) is the maximum*/
return 0;
}
This technique of using one-dimensional array instead of two-dimensional array for recursion and space saving is called "rolling array". Although the above program saves space, it does not reduce the time complexity. The time complexity is still o (N2), as can be seen from the use of two loops in the program.
In the above example, paths from 13 to 8 to 26 to 15 to 24 produce the largest sum of 86.
###Input format:
The first row contains R (1 ≤ R ≤ 1000), indicating the number of rows.
The number of integers contained in a specific row of the pyramid.
All supplied integers are nonnegative and not greater than 100.
###Output format:
A single line containing the largest possible sum.
###Input example:
```in
five
thirteen
11 8
12 7 26
6 14 15 8
12 7 13 24 11
```
###Output example:
```out
eighty-six
```
answer：If there is no answer, please comment
[solution 1]
Triangle data storage generally uses two-dimensional array, as shown in the figure below.
This problem can be solved recursively. The basic idea is: D (I, J) represents the number J in the i-th line (I, J are calculated from 1), and maxsum (I, J) represents the sum of the numbers of the best path from the j-th number in the i-th line to the bottom. That is, to know the maximum value that can be reached at a certain point, we must know the maximum value that can be reached below or at the bottom right. Push to the bottom layer in turn to get the lowest value, and then calculate back to the vertex (1,1) in turn.
Starting from a certain D (I, J), it is obvious that the next step can only be d (I + 1, J) or D (I + 1, j + 1). If we take D (I + 1, J), then we get maxsum (I, J) is maxsum (I + 1, J) + D (I, J); If we take D (I + 1, j + 1), then we get maxsum (I, J) is maxsum (I + 1, j + 1) + D (I, J). So to choose where to go, we need to compare maxsum (I + L, J) and maxsum (I + 1, j + 1) which value is greater.
Reference code:
#include
#define MAX_ NUM 1000
int D[MAX_ NUM + 10][MAX_ NUM + 10];
int N;
Int maxsum (int i, int j) {/ / I is the row and j is the column
if (i == N) // End condition, if to the bottom, return its own value
return D[i][j];
int sum1 = MaxSum(i + 1, j); // If you want to know the maximum value of (I, J) from the left, you must first find the maximum value of the next layer
int sum2 = MaxSum(i + 1, j + 1);// Go down from the right
if (sum1 > sum2)
return sum1 + D[i][j];
return sum2 + D[i][j];
}
int main() {
int i, j;
scanf("%d", &N);
for (i = 1; i <= N; ++ i)
for (j = 1; j <= i; ++ j)
scanf("%d", &D[i][j]);
printf("%d\n", MaxSum(1, 1));
return 0;
}
[solution 2]: memory search
The program above is very inefficient. When n is not large, for example, when n = 100, it is almost impossible to work out the result. Why? It's because of too much double counting. A call to the maxsum (I, J) function may be called "a calculation.". Then, when calculating maxsum (I, J), maxsum (I + 1, J) should be calculated once, and when calculating maxsum (I, J-1), maxsmn (I + 1, J) should also be calculated once, so repeated calculation will occur. For the example given in the title, if the number of times maxsum (I, J) is calculated is written in position (I, J), then the following triangle can be obtained:
one
one one
one two one
one three three one
one four six four one
From the triangle above, This is the coefficient of the binomial, which is Yang Hui's triangle. As you can see, the total number of calculations in the last line is 16, and the total number of calculations in the penultimate line is 8. According to this rule, the complexity of the whole program is O (2n). That is, for n-line triangles, the total number of calculations is 20 + 21 + 22 +... + 2N-1 = 2N-1. When n = 100, 2n is a very large number, no computer can use this program to calculate the result in a person's lifetime.
Since the problem lies in repeated calculation, the only solution is to record a value once it is calculated, so as to avoid unnecessary repeated calculation. That is to say, when calculating the value of maxsum (I, J) for the first time, the value will be stored. When calculating maxsum (I, J) for the next time, you can directly take out the saved value without calling maxsum (I, J) again for recursive calculation. In this way, each maxsmn (I, J) only needs to be calculated once, then the total number of calculations (that is, the number of times to call the maxsum (I, J) function) is the total number of numbers in the triangle, that is, 1 + 2 + 3 +... + n = n ×( N + 1)/2。 The first line has one number, the second line has two numbers,..., and the nth line has n numbers.
How to store the calculated maxsum (I, J) value? It can be solved by using a two-dimensional array did [n] [n]: did [i] [J] stores the calculation results of maxsum (I, J). Next time you need the value of maxsum (I, J), you don't need to call maxsum (I, J) function, just take the value of did [i] [J]. This method is called mnemonic search.
Before giving the code of this method, we use the solution of Fibonacci sequence as an example to illustrate the application of memory search. The following recursive solution to the n-th term of Fibonacci sequence adopts the memory search method.
Code 1: Fibonacci sequence (traditional recursive method)
int fib(int n) {
if (n == 1 || n == 2)
return 1;
return fib(n - 1) + fib(n - 2);
}
The above code runs very slowly when n ≥ 40 and is easy to timeout. It must be optimized as follows:
Code 2: Fibonacci sequence (using memory search)
#include
int arr[47]; // Store intermediate calculation results: global variables, whose initial values are all 0
int fib(int n) {
if (n == 1 || n == 2)
return 1;
if (arr[n] != 0) // If the previous n-th item has been calculated
return arr[n]; // Return the nth item directly
/*
*If the nth item has not been calculated before, the nth item is calculated and the result is stored in the array
*/
return arr[n] = fib(n - 1) + fib(n - 2);
}
int main(void) {
int n;
while (scanf("%d", &n) != EOF) {
printf("%d\n", fib(n));
}
return 0;
}
With the basis of memory search, the reference code for finding the sum of number triangles is given as follows:
#include
#include
#define MAX_ NUM 1000
int D[MAX_ NUM + 10][MAX_ NUM + 10];
int N;
int did[MAX_ NUM + 10][MAX_ NUM + 10]; /* Store intermediate calculation results*/
/*Mnemonic search*/
Int maxsum (int i, int j) {/ * I is the row and j is the column*/
If (I = = n) / * end condition, if it reaches the lowest level, return its own value*/
return D[i][j];
If (did [i + 1] [J] = = 0) / * if maxsum (I + 1, J) has not been calculated*/
did[i + 1][j] = MaxSum(i + 1, j); /* If you want to know the maximum value of (I, J) from the left, you must first find the maximum value of the next layer*/
If (did [i + 1] [J + 1] = = 0) / * if maxsum (I + 1, j + 1) has not been calculated*/
did[i + 1][j + 1] = MaxSum(i + 1, j + 1); /* Go down from the right*/
if (did[i + 1][j] > did[i + 1][j + 1])
return did[i + 1][j] + D[i][j];
return did[i + 1][j + 1] + D[i][j];
}
int main() {
int i, j;
scanf("%d", &N);
/*Setting did to 0 means that all maxsum (I, J) have not been calculated at the beginning*/
memset(did, 0, sizeof(did));
for (i = 1; i <= N; ++ i)
for (j = 1; j <= i; ++ j)
scanf("%d", &D[i][j]);
printf("%d\n", MaxSum(1, 1));
return 0;
}
In the above program, the value of the elements of the did array is only calculated once, and the time taken to calculate once is constant, so the time complexity is O (N2), which is obviously much smaller than o (2n). Even if n = 1000, N2 is only 106. Data of this magnitude is more than enough in one second, and there is no TLE.
[solution 3]
The method of decomposing a problem into subproblems to solve recursively and saving the intermediate results to avoid repeated calculation can be called "dynamic programming". Dynamic programming is usually used to find the optimal solution. The problem of finding the optimal solution that can be solved by dynamic programming must satisfy that every local solution of the optimal solution is also optimal. Taking the above question as an example, each number in the best path to the bottom is the best path from the number to the bottom.
In fact, the idea of recursion does not need to be implemented as a recursive function in programming. In the example above, there is a recurrence formula
D(i,j) , i = N
MaxSum(i,j) =
Max {maxsum (I + 1, J), maxsum (I + 1, j + 1)} + D (I, J), others
It is not necessary to write a recursive function, starting from the element of the last line, it can get the final value of DP [1] [1]. The procedure is as follows:
#include
#include
#define MAX_ NUM 1000
int D[MAX_ NUM + 10][MAX_ NUM + 10]; /* Store digital triangles*/
int N; /* The number of rows of the number triangle*/
int dp[MAX_ NUM + 10][MAX_ NUM + 10]; /* State array*/
int max(int x, int y) {
return x > y ? x : y;
}
int main() {
int i, j;
scanf("%d", &N);
memset(dp, 0, sizeof(dp));/* The state array is all initialized to 0*/
for (i = 1; i <= N; ++ i)
for (j = 1; j <= i; ++ j)
scanf("%d", &D[i][j]); /* Input digital triangle*/
for (j = 1; j <= N; J + +) {/ * process the bottom line*/
dp[N][j] = D[N][j]; /* The value of the bottom row status array is the number itself*/
}
for (i = N - 1; i >= 1; I --) {/ * from the bottom to the top*/
for (j = 1; j <= i; j++) {
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + D[i][j];
}
}
printf("%d\n", dp[1][1]); /* The vertex (1,1) is the maximum value * / s
return 0;
}
As shown in the figure below, the number in the box is the maximum value that can be obtained.
I believe that after reading this diagram, it is not difficult for us to understand dynamic programming.
In fact, because the value of DP [i] [J] is useless after it is used to calculate DP [I - 1] [J], the calculated value of DP [I - 1] [J] can be directly stored in the position of DP [i] [J]. In this way, the calculated DP [n - 1] [1] replaces the original DP [n] [1], the calculated DP [n - 1] [2] replaces the original DP [n] [2]... The calculated DP [n-1] [n-1] replaces the original DP [n] [n-1]. In fact, the DP array only uses the last line to store all the results that should have been stored in the DP [n-1] line in the above program. In the same way, the DP array can store all the intermediate calculation results in the last row, and the final result (which should be DP [l] [l]) can also be stored in DP [n] [1]. Therefore, in fact, DP does not need to be a two-dimensional array, one-dimensional array is enough.
The rewritten procedure is as follows:
#include
#include
#define MAX_ NUM 1000
int D[MAX_ NUM + 10][MAX_ NUM + 10]; /* Store digital triangles*/
int N; /* The number of rows of the number triangle*/
int *dp; /* State array*/
int max(int x, int y) {
return x > y ? x : y;
}
int main() {
int i, j;
scanf("%d", &N);
for (i = 1; i <= N; ++ i)
for (j = 1; j <= i; ++ j)
scanf("%d", &D[i][j]); /* Input digital triangle*/
dp = D[N]; /* DP points to line n*/
for (i = N - 1; i >= 1; I --) {/ * from the bottom to the top*/
for (j = 1; j <= i; j++) {
dp[j] = max(dp[j], dp[j + 1]) + D[i][j];
}
}
printf("%d\n", dp[1]); /* （ 1,1) is the maximum*/
return 0;
}
This technique of using one-dimensional array instead of two-dimensional array for recursion and space saving is called "rolling array". Although the above program saves space, it does not reduce the time complexity. The time complexity is still o (N2), as can be seen from the use of two loops in the program.