数字三角形

程序设计导引及在线实践

第一种解法，直接递归，优化后，改为逆推动态规划

打印路径，可以反过来计算。

#include<iostream>
using namespace std;
#define MAX_NUM 100
int A[MAX_NUM + 10][MAX_NUM + 10];
int D[MAX_NUM + 10][MAX_NUM + 10];
int N;

void print_path()
{
     int i=1,j=1;
     printf("%d ", A[i][j]);

     for(i = 1; i < N; )
     {
         if(D[i][j]==D[i+1][j+1]+A[i][j])
             j=j+1;
         i++;
         printf("%d ", A[i][j]);
     }
     printf(" ");

}
int main()
{
     int m;
     scanf("%d", &N);
     for( int i = 1; i <= N; i ++ )
         for( int j = 1; j <= i; j ++ )
             scanf("%d", &A[i][j]);

    for(int i=1;i<=N;i++)
     {
         D[N][i]=A[N][i];
     }
     for(int i=N-1;i>=1;i--)
     {
         for( int j = 1; j <= i; j ++ )
             D[i][j]=max(D[i+1][j], D[i+1][j+1]) + A[i][j];
     }
     printf("%d ", D[1][1]);
     print_path();
     return 0;
}

另一种是计算时候就保存方向，加一个数组保存相关信息

#include<iostream>
using namespace std;
#define MAX_NUM 100
int A[MAX_NUM + 10][MAX_NUM + 10];
int D[MAX_NUM + 10][MAX_NUM + 10];
int dir[MAX_NUM + 10][MAX_NUM + 10];//保存方向
int N;

}

void print_path2()
{
     int i=1,j=1;
     //printf("%d ", A[i][j]);

     for(i = 1; i <=N; )
     {
         printf("%d ", A[i][j]);
         j+=dir[i][j];
         i++;
     }
     printf(" ");

}
int main()
{
     int m;
     scanf("%d", &N);
     for( int i = 1; i <= N; i ++ )
         for( int j = 1; j <= i; j ++ )
             scanf("%d", &A[i][j]);

    for(int i=1;i<=N;i++)
     {
         D[N][i]=A[N][i];
     }
     for(int i=N-1;i>=1;i--)
     {
         for( int j = 1; j <= i; j ++ )
         {
             if(D[i+1][j] > D[i+1][j+1])
             {
                 D[i][j]=D[i+1][j] + A[i][j];
                 dir[i][j]=0;
             }
             else
             {
                 D[i][j]=D[i+1][j+1] + A[i][j];
                 dir[i][j]=1;
             }

         }

     }
     printf("%d ", D[1][1]);
     print_path();
     print_path2();
     return 0;
}