Dynamic programming - related concepts, (tower problem)

Several concepts related to dynamic programming ：

•    Memory search ： For problems with overlapping subproblems , We record the value of the subproblem we encounter for the first time , Use this value directly the next time you encounter the same sub problem , This is also the recursive function to open a two-dimensional array   The role of ;
•     Overlapping subproblems ： A problem can be divided into several sub problems , These sub problems will recur ;
•     Optimal substructure ： If the optimal solution of a problem can be constructed from the solution of a subproblem ;
• The state has no aftereffect ： The current status records historical information , Once the current state is determined , It won't change , And future decisions can only be made on the basis of one or several existing states , Historical information can only affect future decisions through existing states .（PS：《 Algorithm notes 》）

Give a classic question —— The number of towers ： A total of several procedures are given , With direct solution output , And the path that gives the maximum value , There are also recursive solutions , There are also recursive solutions ：

/**
     The number of towers ,
     State transition equation ：dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
     Optimal substructure ： If the optimal solution of a problem can be constructed from the solution of a subproblem ;
    1) Output results only ;
    data:
        5
        5
        8 3
        12 7 16
        4 10 11 6
        9 5 3 9 4

        5
        5
        8 3
        12 7 105
        4 10 11 6
        78 5 3 9 4
*/

/**
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cout << " Enter the number of floors of the tower :\n";
    cin >> n;
    int f[n+1][n+1],dp[n+1][n+1];
    printf(" Input %d Value of tower floor \n",n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j)
            cin >> f[i][j];
    for(int i=1;i<=n;++i)
        dp[n][i]=f[n][i];
    for(int i=n-1;i>=1;--i)
        for(int j=1;j<=i;++j)
    {
        dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
    }
    cout << dp[1][1] << endl;
    return 0;
}
*/

 

Recursive solution ：

• /**
      2) Recursive solution 
  */
  /**
       Memory search ： For problems with overlapping subproblems , We record the value of the subproblem we encounter for the first time ,
       The next time you encounter the same subproblem, use this value directly , This is also the recursive function to open a two-dimensional array 
       The role of ;
  
       Overlapping subproblems ： A problem can be divided into several sub problems , These sub problems will recur ;
      
       Optimal substructure ： If the optimal solution of a problem can be constructed from the solution of a subproblem ;
  */
  
  /**
  #include <iostream>
  #include <algorithm>
  #include <cstring>
  using namespace std;
  const int maxn=10;
  int f[maxn][maxn],dp[maxn][maxn];
  int n;
  int max_val(int pos,int index)
  {
      memset(*dp,-1,sizeof(dp));
      if(pos==n)
          return f[pos][index]; // If you reach the last layer , Returns the value of this element 
      if(dp[pos][index]!=-1)
          return dp[pos][index];
      else
      {
          dp[pos][index]= max(max_val(pos+1,index),max_val(pos+1,index+1))+f[pos][index]; // If you want to select this element ,
          return dp[pos][index];  // Then compare the maximum sum of the two elements next to each other on the next layer and the subsequent selections , Who will vote and who will 
  
      }
  }
  int main()
  {
      cout << " Enter the number of floors of the tower :\n";
      cin >> n;
      printf(" Input %d Value of tower floor \n",n);
      for(int i=1;i<=n;++i)
          for(int j=1;j<=i;++j)
              cin >> f[i][j];
      cout << max_val(1,1) << endl;
      return 0;
  }
  */

The path to output the maximum value ：

/**
    3) The path to output the maximum value 
*/

/**
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cout << " The number of floors of the tower :\n";
    cin >> n;
    int f[n+1][n+1],dp[n+1][n+1];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j)
            cin >> f[i][j];
    for(int i=1;i<=n;++i)
        dp[n][i]=f[n][i];
    for(int i=n-1;i>=1;--i)
        for(int j=1;j<=i;++j)
    {
        dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
    }
    cout << "maximum result:\n" << dp[1][1] << endl;
    cout << "path of maxmium:\n" ;
    cout << f[1][1];
    for(int i=1,j=1;i<n;++i)
    {
        cout << " -> ";
        int temp=dp[i][j]-f[i][j];
        if(temp==dp[i+1][j])
            cout << f[i+1][j];
        else
            cout << f[i+1][++j];
    }
    cout << endl;
    return 0;
}
*/

Three dimensional arrays store data , Storage , Intermediate treatment , Output in one

/**
     Three dimensional arrays store data , Storage , Intermediate treatment , Output in one 
*/


#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cout << " The number of floors of the tower :\n";
    cin >> n;
    int a[n+1][n+1][3];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j)
        {
            cin >> a[i][j][0];
            a[i][j][2]=0;   // Suppose each layer selects the left element of the next layer 
        }
    for(int i=1;i<=n;++i)
        a[n][i][1]=a[n][i][0];
    for(int i=n-1;i>=1;--i)
        for(int j=1;j<=i;++j)
    {
        a[i][j][1]=max(a[i+1][j][1],a[i+1][j+1][1])+a[i][j][0];
        if(a[i+1][j][1]<a[i+1][j+1][1])
            a[i][j][2]=1;   // If the right element of the next layer is better , Is set to 1, Select the right element of the next layer 
    }

    cout << "maximum result:\n" << a[1][1][1] << endl;
    cout << "path of maxmium:\n" ;
    int i,j;
    for( i=1,j=1;i<=n;++i)
    {
        cout << a[i][j][0];
        if(i!=1||i!=n)
            cout << " -> ";
        j+=a[i][j][2];
    }
    return 0;
}