5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

4

1

2 3

4 5 6

7 8 9 10

1·记忆化搜索

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define max 100
using namespace std;
int a[max][max],bj[max][max];
int SB(int i,int j,int n)
{
	if(bj[i][j]!=0)return bj[i][j];          //从记忆中寻找
	if(i==n){
	bj[i][j]=a[i][j];
	return a[i][j];
}
	else
	{
		bj[i+1][j]=SB( i+1, j, n);              //记忆下来
		bj[i+1][j+1]=SB( i+1, j+1, n);
		if(bj[i+1][j]>bj[i+1][j+1])
		return bj[i+1][j]+a[i][j];
		else
		return bj[i+1][j+1]+a[i][j];
	}
}
int main()
{
	int n,i,j;
	cin>>n;
	memset(bj,0,sizeof(bj));
	for(i=1;i<=n;i++)
	for(j=1;j<=i;j++)
	cin>>a[i][j];
	printf("%d\n",SB(1,1,n));
}

2·循环算法

#include<iostream>
#include<cstring>
using namespace std;
#define max 100
int a[max][max];
int opt[max][max];
void maxsum(int n)
{
	int i,j;
	opt[0][0]=a[0][0];
	for(i=1;i<n;i++)
	{
		opt[i][0]=opt[i-1][0]+a[i][0];      /***************************
		for(j=1;j<=i-1;j++)
		if(a[i][j]+opt[i-1][j]>=a[i][j]+opt[i-1][j-1])
		opt[i][j]=a[i][j]+opt[i-1][j];
		else                                 分别计算数组到达每一位时的最大值
		opt[i][j]=a[i][j]+opt[i-1][j-1];
		opt[i][i]=opt[i-1][i-1]+a[i][i];    //确保标记每一位数值
                                             
                                            ***************************/
	}
 }
 int main()
 {
 	int i,j,t;
 	int n;
 	cin>>n;
 	memset(opt,0,sizeof(opt));
 	for(i=0;i<n;i++)
 	for(j=0;j<=i;j++)
 	cin>>a[i][j];
 	maxsum(n);
 	t=0;
 	for(i=0;i<n;i++)
 	if(opt[n-1][i]>t)t=opt[n-1][i];
 	printf("%d\n",t);
  }