 # Number of towers - classic example

Posted on Oct. 12, 2023, 7:43 p.m. by Karen Wallace
Category: c++

A classic example of DP algorithm is the tower problem, which is described as follows:

There is a tower of numbers as shown below, and it is required to go from the top to the bottom. If each step can only go to adjacent nodes, what is the maximum sum of the numbers of the nodes it passes through?

I have told you, this is a DP topic, can you AC? The first line of each test instance is an integer N(1 = N = 100), which represents the height of the tower. Next, the tower is represented by N rows of numbers, where line I has I integers, and all integers are within the interval [0,99]. For each test instance, the Output is the maximum sum that can be obtained, and the Output of each instance is one row. Sample Input 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30

In this paper, dynamic programming and improved depth-first algorithm (memorized search) are used

``/ / (dp, Find a recursion ans [I] [j] = Max (ans [j], [I + 1] ans [I + 1] [j + 1]) + itself a [I] [j]) / / # include  iostream  / / # include  algorithm  / / # include  string  //#includestring.h //#includecstdio //#includequeue //#includestack //#includeset //#includemap //#includevector //using namespace std; //int ans,a; //int main(){ // int t = 0; // cin  t; // while(t--){ // int n = 0; // cin  n; // memset(ans,0,sizeof(ans)); // for(int i=1; i=n; i++){ // for(int j=1; j=i; j++){ // cin  a[i][j]; } for(int I =n;} for(int I =n; i=1; i--){ // for(int j=1; j=i; j++){ // ans[i][j] = max(ans[i+1][j],ans[i+1][j+1])+a[i][j]; } // cout  ans  endl; // cout  ans  endl; // return 0; // return 0; // return 0; / /}``

``//#includeiostream //#includealgorithm //#includestring //#includestring.h //#includecstdio //#includequeue //#includestack //#includeset //#includemap //#includevector //using namespace std; //int n; //int ans,a; //int DFS (int I,int j){// if(I == n){// return ans[I][j] = a[I][j]; If (ans[I][j]=0){if(ans[I][j]=0){if(ans[I][j]=0){if(ans[I][j]=0){if(ans[I][j]=0){ // return ans[I][j]; // DFS is normal without this if statement, Return ans[I][j] = Max (DFS (I +1,j+1), DFS (I +1,j+1)) + a[I][j]; //} //int main(){ // int t = 0; // cin  t; // while(t--){ // cin  n; // memset(ans,-1,sizeof(ans)); // for(int i=1; i=n; i++){ // for(int j=1; j=i; j++){ // cin  a[i][j]; } //} // cout  DFS (1,1)  endl; // start from the start DFS //} return 0; / /}``

Search