数字三角形.txt

ACM资料大集合

#include <iostream>
#include <stdio.h>
using namespace std;

#define MAX 10000
int f[10][10];//f[i][j],从顶点到第i行第j列点的最大路径
int thi[10][10];//三角形的点的值
//数字三角形 动态规划
/*
输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出：
30
*/
int cal(int num)
{
	int i,j,max;
	f[1][1]=thi[1][1];
	for(i=2;i<=num;i++)
	{
		for(j=1;j<=i;j++)
		{
			if(j==1) f[i][j]=f[i-1][j]+thi[i][j];
			else if(j==i) f[i][j]=f[i-1][j-1]+thi[i][j];
			else 
			{
				if(f[i-1][j-1]>f[i-1][j]) f[i][j]=f[i-1][j-1]+thi[i][j];//从左上角下来
				else f[i][j]=f[i-1][j]+thi[i][j];//从上面下来
			}
		}
	}
	max=0;
	for(j=1;j<=num;j++)
		if(max<f[num][j]) max=f[num][j];
	return max;
}


int main()
{
	int num,i,j;
	cin>>num;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=i;j++)
			cin>>thi[i][j];
	}
	cout<<cal(num)<<endl;
	return 0;
}