7

              3 8

             8 1 0

            2 7 7 4

           5 5 2 6 5

示出了一個數(shù)字三角形寶塔。數(shù)字三角形中的數(shù)字為不超過100的正整數(shù)。現(xiàn)規(guī)定從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。假設(shè)三角形行數(shù)≤100，編程求解從最頂層走到最底層的一條路徑，使得沿著該路徑所經(jīng)過的數(shù)字的總和最大，輸出最大值。輸人數(shù)據(jù)：由文件輸入數(shù)據(jù)，文件第一行是三角形的行數(shù)N。以后的N行分別是從最頂層到最底層的每一層中的數(shù)字。
如輸入： 5
7           
3 8         
8 1 0     
2 7 7 4     
4 5 2 6 5   
輸出：30

【分析】對于這一問題，很容易想到用枚舉的方法（深度搜索法）去解決，即列舉出所有路徑并記錄每一條路徑所經(jīng)過的數(shù)字總和，然后尋找最大的數(shù)字總和

  1#include<stdio.h>
  2#include<stdlib.h>
  3#include<iostream>
  4using namespace std;
  5#define MAX 100
  6int a[MAX][MAX];
  7int f[MAX][MAX];
  8int map[MAX][MAX];
  9int main()
 10{
 11    int i,j,n,min;
 12    while(scanf("%d",&n)!=EOF)
 13    {
 14        int c,b=n;
 15        /**//*以下為輸入方式*/
 16        for(i=1;i<=n;i++)
 17        {
 18            for(j=1;j<=i;j++)
 19            {
 20                scanf("%d",&a[i][j]);
 21                f[i][j]=a[i][j];
 22            }
 23        }
 24        //初始化f[1][1];
 25        f[1][1]=a[1][1];
 26        //為表圖做標(biāo)記；
 27        for(i=2;i<=n;i++)
 28        {
 29            
 30            f[i][1]=f[i-1][1]+a[i][1];
 31            map[i][0]=0;
 32            f[i][i]=f[i-1][i-1]+a[i][i];
 33            map[i][i]=1;
 34        }
 35        /**//*動態(tài)規(guī)劃選出最優(yōu)解
 36        狀態(tài)方程組：f[i][j]=min(f[i-1][j]+a[i][j],f[i-1][j-1],a[i][j])
 37        */
 38        for(i=3;i<=n;i++)
 39        {
 40            for(j=2;j<=i-1;j++)
 41            {
 42                f[i][j]=f[i-1][j-1]+a[i][j];
 43                map[i][j]=1;
 44                if(f[i][j]>(f[i-1][j]+a[i][j]))
 45                {
 46                    f[i][j]=f[i-1][j]+a[i][j];
 47                    map[i][j]=0;
 48
 49                }
 50            }
 51        }
 52        //選出最優(yōu)解
 53        min=f[n][n];
 54        for(i=1;i<n;i++)
 55        {
 56            if(f[n][i]<min)
 57            {
 58                min=f[n][i];
 59                c=n;
 60                b=i;
 61            }
 62
 63        }
 64        //以下為輸出
 65        printf("%d\n",min);
 66        for(i=1;i<=n;i++)
 67        {
 68            for(j=1;j<=i;j++)
 69            {
 70                if(map[i][j]==0)
 71                    printf("| ");
 72                else if(map[i][j]==1)
 73                        printf("\\ ");
 74                    else
 75                {
 76                    printf("  ");
 77                }
 78            }
 79            printf("\n");
 80        }
 81        //倒序輸出所有選中項a[i][j]
 82        printf("倒序輸出所選中的a[i][j]有：");
 83        while(c!=1||b!=1)
 84        {
 85            printf("%d ",a[c][b]);
 86            if(map[c][b]==0)
 87            {
 88                c=c-1;
 89            }
 90            else if(map[c][b]==1)
 91            {
 92                c=c-1;
 93                b=b-1;
 94            }
 95        }
 96        printf("%d\n",a[1][1]);
 97
 98    }    
 99return 0;
100}