2584: 蓝桥杯2020年第十一届省赛真题-数字三角形 C++

解题思路:

思路：相比于简单地查找动态规划查找最大路径，该题多了一个左移右移的限制，看似是多了一个条件，实则使得题目更加简单了

1)当数字三角形有奇数行时，我们需要走偶数步，所以左移步数和右移步数一定相同，最后一定会到达最后一层中间的那个点

2)当数字三角形有偶数行时，我们需要走奇数步，所以左移和右移步数差绝对值一定为1，最后一定走到最后一层中间两个点中的一个

因此可以得出N%2==1时从(N,N/2+1)开始向上搜索，N%2==0时，从(N,N/2),(N,N/2+1)开始向上搜索取其中大的那个

我们仅需要从底层的目标点向上进行搜索，并且在搜索过程中不用考虑步数限制

注意事项:

为了防止时间爆掉，采用记忆化递归
参考代码:

#pragma optimize(1)
#pragma optimize(2)
#pragma optimize(3,"Ofast","inline")
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int N;//表示数字三角形行数 
int ans=0;//存储搜索结果 
int triangle[101][101]={0};//存储数字三角形
int dp[101][101]={0};//dp[i][j]表示从数字三角形第i行第j列到顶端的最大路径 
int MAX_route(int i,int j){//求 数字三角形第i行第j列到顶端的最大路径 
    //记忆化递归 ,从底层开始向上搜索 
	if(i==1) return triangle[1][1];//递归到顶端直接返回顶端值 
	if(dp[i][j]!=0) return dp[i][j];// 该值已计算出，直接返回 
	int left=-1,right=-1;//left代表往左上点的最大路径，right代表右上点的最大路径 
	if(i!=1){//存在左上路径 
		left=MAX_route(i-1,j-1);
	} 
	if(i!=j){//存在右上路径 
		right=MAX_route(i-1,j); 
	}
	dp[i][j]=max(left,right)+triangle[i][j];
	return dp[i][j];
}
int main(){
	cin>>N;
	for(int i=1;i<=N;++i){
		for(int j=1;j<=i;++j){
			cin>>triangle[i][j];
		}
	} 
	if(N%2){//奇数行的数字三角形 
		ans=MAX_route(N,N/2+1); 
	}
	else{
		ans=max(MAX_route(N,N/2),MAX_route(N,N/2+1));
	}
	cout<<ans;
	return 0;
	}