OJ:数字三角形(搜索)

发布于:2024-04-21 ⋅ 阅读:(161) ⋅ 点赞:(0)

🎁个人主页我们的五年

🔍系列专栏每日一练

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

🌷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行的大小,哪个数大就加上哪个数。


网站公告

今日签到

点亮在社区的每一天
去签到