博客

题目

总时间限制: 1000ms 内存限制: 65536kB

描述

图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

输入

输入的是一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

输出

输出最大的和。

样例输入

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

样例输出

30

递归的方法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NUM 100
int D[MAX_NUM+10] [MAX_NUM+10];
int N;//行数 
int aMaxSum[MAX_NUM+10][MAX_NUM+10];
int MaxSum(int r,int j){
	if(r==N){//递归的出口 
		return D[r][j]; 
	}
	/*
	*每次计算完做上标记，减少重复计算的次数 
	*aMaxSum用来存放计算后的结果，-1为没有走过的路径 
	*/
	if(aMaxSum[r+1][j]==-1){
		aMaxSum[r+1][j] = MaxSum(r+1,j);
	}
	if(aMaxSum[r+1][j+1]==-1){
		aMaxSum[r+1][j+1] = MaxSum(r+1,j+1);
	}
	//判断哪条路径的值大就走那边 
	if(aMaxSum[r+1][j]>aMaxSum[r+1][j+1]){
		return aMaxSum[r+1][j] + D[r][j];
	}
	return aMaxSum[r+1][j+1] + D[r][j];
}

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char *argv[]) {
	int m,i,j;
	scanf("%d",&N);
	memset(aMaxSum,-1,sizeof(aMaxSum));//将 aMaxSum全部置为-1，表示没用算过 
	for(i=1;i<=N;i++){
		for(j=1;j<=i;j++){
			scanf("%d",&D[i][j]);
		}
	}
	printf("%d",MaxSum(1,1));
	return 0;
}

递推

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NUM 100
int D[MAX_NUM+10] [MAX_NUM+10];
int N;//行数 
int aMaxSum[MAX_NUM+10][MAX_NUM+10];

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char *argv[]) {
	int m,i,j;
	scanf("%d",&m);
	for(i=1;i<=m;i++){
		for(j=1;j<=i;j++){
			scanf("%d",&D[i][j]);
		}
	}
	for(i=1;i<=m;i++){
		aMaxSum[m][i] = D[m][i];
	}
	for(i=m-1;i>=1;i--){
		for(j=1;j<=i;j++){
			int nSum1 = D[i][j]+aMaxSum[i+1][j];
			int nSum2 = D[i][j]+aMaxSum[i+1][j+1];
			if(nSum1>nSum2){
				aMaxSum[i][j] = nSum1;
			}else{
				aMaxSum[i][j] = nSum2;
			}
		}
	}
	printf("%d",aMaxSum[1][1]);
	return 0;
}