蓝桥杯 算法训练之数字三角形（dp）

AC代码如下：

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100+2;int g[maxn][maxn];int d[maxn][maxn];int n;int solve(int x,int y){	int& ans=d[x][y];	if(ans>0)return d[x][y]; //如果当前子树已经在之前计算了，就不在计算，直接用就行了	if(x==n-1)return g[x][y]; //到达边界	return ans=g[x][y]+max(solve(x+1,y),solve(x+1,y+1));}int main(){	while(scanf("%d",&n)==1){		for(int i=0;i<n;i++)			for(int j=0;j<i+1;j++)				scanf("%d",&g[i][j]);			memset(d,0,sizeof(d));			int ans=solve(0,0);			PRintf("%d/n",ans);	}	return 0;} 2、递推计算：
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100+2;int g[maxn][maxn];int d[maxn][maxn];int main(){	int n;	while(scanf("%d",&n)==1){	for(int i=0;i<n;i++)		for(int j=0;j<i+1;j++)			scanf("%d",&g[i][j]);		memset(d,0,sizeof(d));	for(int i=n-1;i>=0;i--)       //逆序枚举，就不会重复计算子树		for(int j=0;j<i+1;j++){			d[i][j]=g[i][j]+max(d[i+1][j],d[i+1][j+1]);		}		printf("%d/n",d[0][0]);	}	return 0;}