OJ：数字三角形（搜索）

🎁个人主页：我们的五年

🔍系列专栏：每日一练

🌷追光的人，终会万丈光芒

🌷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];
int max=0;    //max表示最大值
int n;
int dx[]={1,1},dy[]={0,1};
void fun(int x,int y,int sum)
{
    if(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]);
        }
    }
    fun(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.递归：

该题解应用dfs，对所以情况都一一列举了一下

从1,1位置开始，每次只能向下，或者右下，所以只要考虑x到达n行的位置，就可以计算sum的值。

2.循环+数组：

从第n行开始，去确定n-1行的大小，哪个数大就加上哪个数。