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 > //#include<string.h> //#include<cstdio> //#include<queue> //#include<stack> //#include<set> //#include<map> //#include<vector> //using namespace std; //int ans[105][105],a[105][105]; //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[1][1] << endl; // cout << ans[1][1] << endl; // return 0; // return 0; // return 0; / /}
//#include<iostream> //#include<algorithm> //#include<string> //#include<string.h> //#include<cstdio> //#include<queue> //#include<stack> //#include<set> //#include<map> //#include<vector> //using namespace std; //int n; //int ans[105][105],a[105][105]; //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; / /}