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