Question

数字三角形问题，动态规划法，C语言编写

从数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大，路径上的每一步都只能往左下或右下走。共有n行，由文件input.txt给出输入数据，文件第一行为行数n，各行中的数字在0~99之间。程序运行结束，将结果输出到文件output.txt中，其中第一行为计算最大值。
求大神给出c代码，并用txt格式将代码发送到164625109@qq.com.感谢!

Answer 1

/************************************************************************/
/****************************** UESTC xiaobo ****************************/
/************************************************************************/

# include <stdio.h>
# include <stdlib.h>
# define N (50)

int data[N*N];
int mat[N][N];
int max[N][N];

void print(int m[][N], int row, int col)
{
	int i,j;
	for(i=0;i<row;i++)
	{
		for(j=0;j<col;j++)
		{
			printf("%d\t",m[i][j]);
		}
		printf("\n");
	}
}

/************************************************************************/
/*	动态规划:	max[x][y]=mat[x][y]+max(mat[x+1][y-1],mat[x+1][y+1])	*/
/************************************************************************/
int getMax(int m[][N], int row, int col)
{
	int i,j;
	int ans;

	for(j=0;j<col;j++)
	{
		max[0][j]=m[0][j];
	}

	for(i=1;i<row;i++)
	{
		for(j=0;j<col;j++)
		{
			if(j==0)
			{
				max[i][j]=mat[i][j]+max[i-1][j+1];
			}
			else if(j==col-1)
			{
				max[i][j]=mat[i][j]+max[i-1][j-1];
			}
			else
			{
				if(mat[i-1][j-1]>mat[i-1][j+1])
				{
					max[i][j]=mat[i][j]+max[i-1][j-1];
				}
				else
				{
					max[i][j]=mat[i][j]+max[i-1][j+1];
				}
			}
		}
	}

	print(max,row,col);
	ans=max[row-1][0];
	for(j=1;j<col;j++)
	{
		if(max[row-1][j]>ans)
		{
			ans=max[row-1][j];
		}
	}

	return ans;
}

int main()
{
	int i,j;
	int row,col;
	int count=0;
	int temp;
	int ans;
	FILE *fin=fopen("input.txt","r");
	FILE *fout=fopen("output.txt","w");
	if(fin==NULL)
	{
		perror("input.txt");
		exit(EXIT_FAILURE);
	}
	if(fout==NULL)
	{
		perror("output.txt");
		exit(EXIT_FAILURE);
	}

	fscanf(fin,"%d",&row);
	while(fscanf(fin,"%d",&temp)!=EOF)
	{
		data[count++]=temp;
	}

	col=count/row;
	if(col<2)
	{
		printf("input error!");
		exit(EXIT_FAILURE);
	}
	
	for(i=0;i<row;i++)
	{
		for(j=0;j<col;j++)
		{
			mat[i][j]=data[i*col+j];
			printf("%d\t",mat[i][j]);
		}
		printf("\n");
	}
	printf("\n");

	ans=getMax(mat,row,col);
	printf("\nans: %d\n",ans);
	fprintf(fout,"%d",ans);

	fclose(fin);
	fclose(fout);

	system("pause");
	return 0;
}