OJ：数字三角形（搜索）

前言： 每日一练专栏分享我的在刷题中不太熟练，不太会的问题，系列专栏请点击： 🔍系列专栏：每日一练 或者点开我的主页，然后进入我的专栏，喜欢的可以点击订阅我的专栏，也希望得到大家的三连。 该文提供了我的两种解题方法，一种暴力（dfs）求解和循环求解。 有任何错误的地方，请大佬们及时帮我指出来，我会尽快修改。

🌷1.问题描述：

⛳️题目描述： 示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路 径，使该路径所经过的数字的总和最大。  每一步可沿左斜线向下或右斜线向下走；  1< 三角形行数< 25；  三角形中的数字为整数< 1000； ❗️每次移动只能向下，或者向右下

⛳️输入格式： 第一行为N，表示有N行 后面N行表示三角形每条路的路径权

⛳️输出格式： 路径所经过的数字的总和最大的答案

⛳️输入样例：

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

⛳️输出样例：

30

🌷2.实现代码：

方法一：递归

#include<stdio.h>
#include<math.h>
int s[30][30];  //定义一个30,30的数组
int max=0;    //max表示最大值
int n;
int dx[]={1,1},dy[]={0,1};  //每次移动有两种情况
void dfs(int x,int y,int sum)
{
    if(x==n)  //如果x到达n表示到达了三角形底部
    {
        sum+=s[x][y];    //最后加上最后一个数字
        if(sum>max)
            max=sum;
    }
    else
    {
        sum+=s[x][y];
        fun(x+dx[0],y+dy[0],sum);    //两种移动的情况
        fun(x+dx[1],y+dy[1],sum);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            scanf("%d",&s[i][j]);    //输入三角形
        }
    }
    dfs(1,1,0);
    printf("%d",max);
    return 0;
}

方法二：循环+数组

#include<stdio.h>
#include<math.h>
int main()
{
	int n;
	scanf("%d",&n);
	int s[40][40]={0};
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			scanf("%d",&s[i][j]);
		}
	}
	for(int i=n;i>=1;i--)
	{
		for(int j=1;j<i;j++)
		{
			if(s[i][j]>s[i][j+1])
				s[i-1][j]+=s[i][j];
			else
				s[i-1][j]+=s[i][j+1];
		}
	}
	printf("%d",s[1][1]);
    return 0;
}

🌷 3.代码分析：

方法一：递归

⛷1.int s[30][30]={0}; 我们先定义一个全局二维数组，大小为30*30，因为题目中说1<三角形行数<25,所以定义30是完全足够了的。

⛷2. scanf("%d",&n); for(int i=1;i<=n;i++) //三角形行数 { for(int j=1;j<=i;j++) //第几个数 { scanf("%d",&s[i][j]); //输入三角形 } } 输入全局变量n，两个循环输入三角形，i代表三角形行数,j代表是第几个数，第i行的元素应该是i个，所以j<=i.

⛷3.int dx[]={1,1},dy[]={0,1}; //每次移动有两种情况 每次移动只有两种情况，每次必须往下走，所以dx[]={1,1} 行数x必须+1，列可以+1，也可以不变，dy[]={0,1}

⛷4.void dfs(int x,int y,int sum) { if(x==n) //如果x到达n表示到达了三角形底部 { sum+=s[x][y]; //最后加上最后一个数字 if(sum>max) max=sum; } else { sum+=s[x][y]; fun(x+dx[0],y+dy[0],sum); //两种移动的情况 fun(x+dx[1],y+dy[1],sum); } } dfs函数中，我们先判断x是不是为n，如果为n那么就到达三角形的最后一行，只需加上此时的最后一个数就是这条路径的和，如果比max大，我们就更新max的值为sum。 如果x不为n，那么，那么就sum加上此时的数，然后往下走，往想走又分两种情况 最后所以路径都走完以后，就可以得到最大的sum，最后输出max。

方法二：循环

方法二的前面都是一样的，最主要的是： for(int i=n;i>=1;i--) { for(int j=1;j<i;j++) { if(s[i][j]>s[i][j+1]) s[i-1][j]+=s[i][j]; else s[i-1][j]+=s[i][j+1]; } } 从n行开始，因为n-1行的每一个数从n-1走到n行，只有两种可能，所以只要比较两个情况哪个数大，就加哪个数。最后第一行第一个就是最大的数和。

🌷总结：

两种方法给我们提供了不同的解题方向，第一种就是暴力求解，只要掌握基本逻辑，第二种循环才是要培养的思维方式。

最后感谢大家的阅读。