1311: 数字三角形 通过递归函数dfs来进行深度优先搜索

解题思路:

代码中定义了一个二维数组dp来存储三角形的数值。然后，通过递归函数dfs来进行深度优先搜索。函数中的参数p1表示当前所在的行数，p2表示当前所在的列数，sum表示当前路径的和。

在递归函数中，首先判断是否到达了三角形的最底部（即p1==n），如果是，则更新最大路径和Max。然后，根据题目要求，分别向右斜方向和左斜方向进行递归调用，并更新路径和。

最后，在主函数中，首先读入三角形的数值，并调用dfs函数进行求解。最终输出最大路径和Max。

注意事项:

参考代码:

#include<bits/stdc++.h>//万能头
using namespace std;

const int N=1002;
int dp[N][N]={0};
int Max=0;//最大路径和Max
int n;
void dfs(int p1,int p2,int sum){
	if(p1==n){//到达了三角形的最底部（即p1==n），更新最大路径和Max
	    if(Max<sum){
		Max=sum;	
	    }
	    return ;	
	}
	//右斜 
	dfs(p1+1,p2+1,sum+dp[p1+1][p2+1]);
	//左斜 
	dfs(p1+1,p2,sum+dp[p1+1][p2]);
}

int main()
{
	cin>>n;
	int i,j;
	for(i=1;i<=n;i++){
	    for(j=1;j<=i;j++){
		cin>>dp[i][j];
            }
	}
	dfs(1,1,dp[1][1]);
	cout<<Max;
}