1177: 三角形（递归，记忆型递归，递推）

解题思路:

递归：
从上往下走，每一次只走和最大的路，最后的值就是最大的

#include <stdio.h>
#define MAX 101
#define max(x,y) ((x)>(y)?(x):(y))

int n;
int p[MAX][MAX];

int sum(int i,int j){
	if(i==n-1)return p[i][j];
	int x=sum(i+1,j);
	int y=sum(i+1,j+1);
	return max(x,y)+p[i][j];
}

int main ()
{
	int i,j;
	int x;
	scanf("%d",&x);
	while(x--){
		scanf("%d",&n);
		for(i=0;i<n;i++){
			for(j=0;j<i+1;j++){
				scanf("%d",&p[i][j]);
			}
		}	
		printf("%d\n",sum(0,0));
	}
	
	return 0;
}

但是这样会时间超限，因为每一个节点会被重复计算，时间复杂度大概为2^n，是指数级增长，为了避免重复计算，使用记忆型递归

代码实现如下：

#include <stdio.h>
#define MAX 101
#define max(x,y) ((x)>(y)?(x):(y))

int n;
int p[MAX][MAX];
int m[MAX][MAX];

int sum(int i,int j){
	if(m[i][j]!=-1)return m[i][j];//如果不是-1说明已经计算过，可以直接返回值不用再计算
	if(i==n-1){
		m[i][j]=p[i][j];
	}else{
		int x=sum(i+1,j);
		int y=sum(i+1,j+1);
		m[i][j]=max(x,y)+p[i][j];
	}
	return m[i][j];
}

int main ()
{
	int i,j;
	int x;
	scanf("%d",&x);
	while(x--){
		scanf("%d",&n);
		for(i=0;i<n;i++){
			for(j=0;j<i+1;j++){
				scanf("%d",&p[i][j]);
				m[i][j]=-1;//初始化为-1
			}
		}	
		printf("%d\n",sum(0,0));
	}
	
	return 0;
}

这样的时间复杂度是n^2，因为数据规模最大是100，可以很轻松通过

最后是不用递归的递推法，这是从下往上的走法，我们用另一个数组储存数字三角形最底层一行的值，每次通过用最底层的最优值 来计算上一层的最优值

代码实现如下：

#include <stdio.h>
#define MAX 101
#define max(x,y) ((x)>(y)?(x):(y))

int n;
int p[MAX][MAX];
int m[MAX][MAX];

int main ()
{
	int i,j;
	int x;
	scanf("%d",&x);
	while(x--){
		scanf("%d",&n);
		for(i=0;i<n;i++){
			for(j=0;j<i+1;j++){
				scanf("%d",&p[i][j]);
				if(i==n-1){
					m[i][j]=p[i][j];//将最底层的数复制到m内 
				}
			}
		}
		for(i=n-2;i>=0;i--){
			for(j=0;j<i+1;j++){
				m[i][j]=max(m[i+1][j],m[i+1][j+1])+p[i][j];
			}
		} 
		printf("%d\n",m[0][0]);
	}
	
	return 0;
}