【C语言蓝桥杯每日一题】——数字三角形

【C语言蓝桥杯每日一题】—— 数字三角形😎

前言🙌
- 数字三角形🙌
总结撒花💞

😎博客昵称：博客小梦
😊最喜欢的座右铭：全神贯注的上吧！！！
😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！
😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘

前言🙌

哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘我仅已此文，和大家分享【C语言蓝桥杯每日一题】—— 数字三角形~ 都是精华内容，可不要错过哟！！！😍😍😍

数字三角形🙌

题目描述
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

在这里插入图片描述

解题思路分析： 😍

首先认真读题，然后分析，找出规律
因为一般线上平台是支持变长数组的，所以这里我创建了一个变长二维数组 arr（就是【】里面是变量，可以根据输入的n值变化而变化的数组。
首先先利用两层循环进行三角形数值的存储。
在利用两层循环进行三角形的遍历，其实就是对二维数组的遍历。
然后看图分析，我们可以发现到，从第二行开始，第一个的元素上面没有左上角的值，直接加上面的值就是最大值。
最后一个元素没有正上方的值，直接加左上值即可。
其余情况加其左上右上的最大值
利用一个三目运算符，我们封装设计一个比较两个数最大值的函数。
由于题目要求，向左下走的次数与向右下走的次数相差不能超过 1。即输出第n行最中间二个的最大值。那么就要就要判断三角形有多少行了。如果n为奇数，那么最中间那个就是答案。如果是偶数行，那么最中间的两个数的最大值就是所求的答案。

#include <stdio.h>
#include <stdlib.h>
int Max(int x , int y)
{
  return x > y ? x : y;
}

int main(int argc, char *argv[])
{
  int n = 0;
  scanf("%d",&n);
  int arr[n][n];
  int i = 0;
  int j = 0;
  for (i = 0; i < n; i++)
  {
    for (j = 0; j <= i; j++)
    {
      scanf("%d",&arr[i][j]);
    }
  }

  for (i = 0; i < n; i++)
  {
    for (j = 0; j <= i; j++)
    {
      if(i >=  1)
      {
        if(j == 0)
        arr[i][j] += arr[i - 1][j];
        else if(i == j)
        arr[i][j] += arr[i - 1][j - 1];
        else
        {
          int max = Max(arr[i - 1][j - 1],arr[i - 1][j]);
          arr[i][j] += max;
        }
      }
    }
  }

  if( n % 2 == 1)
  printf("%d",arr[n - 1][(n - 1) / 2]);
  else
  printf("%d",Max(arr[n - 1][(n - 1) / 2],arr[n - 1][(n - 1) / 2 + 1]));
  return 0;
}