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

缺乏、安全感 2024-02-17 19:13 72阅读 0赞

算法训练 数字三角形

时间限制：1.0s 内存限制：256.0MB

问题描述

（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路  
　　径，使该路径所经过的数字的总和最大。  
　　●每一步可沿左斜线向下或右斜线向下走；  
　　●1＜三角形行数≤100；  
　　●三角形中的数字为整数0，1，…99；  
  
  
　　 ![RequireFile.do_fid_9RdAy6Be][].  
　　（图３.１－１）

输入格式

文件中首先读到的是三角形的行数。  
  
　　接下来描述整个三角形

输出格式

最大总和（整数）

样例输入

5  
7  
3 8  
8 1 0  
2 7 4 4  
4 5 2 6 5

样例输出

AC代码如下：

1、记忆化搜索：

#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;
    }

[RequireFile.do_fid_9RdAy6Be]: http://lx.lanqiao.cn/RequireFile.do?fid=9RdAy6Be