#include<stdio.h>

#include<string.h>

int a[105][105],f[105][105];

int max(int a,int b)

{

    return a>b?a:b;

}

int main()

{

    int i,j,n,k;

    while(scanf("%d",&n)!=EOF){

        for(i=1;i<=n;i++)

            for(j=1;j<=i;j++)

                scanf("%d",&a[i][j]);

        memset(f,0,sizeof(f));

        k=0;

        f[1][1]=a[1][1];   //第一个数肯定要加

        for(i=2;i<=n;i++){

            for(j=1;j<=i;j++){

                if(j==1)                      //在左边界时

                    f[i][j]=f[i-1][j]+a[i][j];

                else if(j==i)                     //在右边界时

                    f[i][j]=f[i-1][j-1]+a[i][j];

                else                               //不在边界时

                    f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];

            }

        }

        for(i=1;i<=n;i++)           //比較全部可能的大小

            k=max(k,f[n][i]);

        printf("%d\n",k);

    }

    return 0;

}

优化后：

#include<stdio.h>

#include<string.h>

int max(int a,int b)

{

    return a>b?a:b;

}

int main()

{

    int i,j,n,k,f[105][105];

    while(scanf("%d",&n)!=EOF){

        memset(f,0,sizeof(f));    //初始化为0

        for(i=1;i<=n;i++)

            for(j=1;j<=i;j++)

                scanf("%d",&f[i][j]);

        k=0;

        for(i=2;i<=n;i++)

            for(j=1;j<=i;j++)

                f[i][j]+=max(f[i-1][j-1],f[i-1][j]); //由于在边界左右没数的地方都初始化为0了。加上后不会产生影响

        for(i=1;i<=n;i++)

            k=max(k,f[n][i]);

        printf("%d\n",k);

    }

    return 0;

}

链接：poj 3176