🎁个人主页：我们的五年

🔍系列专栏：每日一练

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

🌷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];elses[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行的大小，哪个数大就加上哪个数。