当前位置: 首页 > article >正文

【蓝桥杯】 C++ 数字三角形 动态规划 ⭐⭐

文章目录

    • 题目描述
      • 输入描述
      • 输出描述
    • 实现代码
    • 解题思路
    • 注意点
    • 知识点

题目描述

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和(路径上的每一步只可沿左斜线向下或右斜线向下走)。
在这里插入图片描述

输入描述

输入的第一行包含一个整数 N (1≤N≤100),表示三角形的行数。下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 99 之间的整数。

输出描述

输出一个整数,表示答案。

实现代码

#include<bits/stdc++.h>
using namespace std;

#define N 101

int main()
{
    int n;
    cin>>n;
    int tri[N][N]={0};  // 存输入的三角形
    int dp[N][N]={0};   // 存动态规划算出来的数,到达每一个点最大的和

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>tri[i][j];
        }
    }

    // 要算 dp[i][j] ,就得知道 tri[i][j]和 dp[i-1][j] 和 dp[i-1][j-1] 中哪个最大
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+tri[i][j];
        }
    }

    int ans=dp[n][1];
    for(int i=1;i<=n;i++)
    {
        if(dp[n][i]>ans)
        {
            ans=dp[n][i];
        }
    }
    cout<<ans;
    return 0;
}

解题思路

这个题是动态规划的题目,首先根据题意发现这个和递归很像,通过子问题堆叠可以推出要求解的问题,同时动态规划通常用于最优解问题,解决这个问题比较方便。

  1. 把数字三角形存入二维数组,待后续取用。
  2. 把三角形变成直角三角形,如下图,可以发现要求第三行的 “1” 的最大ans,就需要知道第二行 “3” 和 “8” 的最大 ans,取较大的 ans,因此可得到达每一个点的 dp[ i ] [ j ] = dp[ i-1 ] [ j-1 ] + dp[ i-1 ] [ j ] + tri[ i ] [ j ],
  3. 最后比较最后一行的每个数的ans,取最大即可得到答案。
    在这里插入图片描述

注意点

  • 注意 tridp 要开101个,不知道为什么,如果开 n+1 个的话,结果就不对……
  • 注意 dp[ i ][ j ] 的算法,加完上面最大的ans之后,还需要加 tri[ i ] [ j ] 的值。

知识点

  • 动态规划文章:看一遍就理解:动态规划详解 、 动态规划和递归的区别 。根据下面的代码可以更加直观地理解动态规划和递归的区别与相似之处。
    在这里插入图片描述

http://www.kler.cn/a/2368.html

相关文章:

  • spring学习(spring-DI(setter注入、构造器注入、自动装配方式))
  • 【WRF教程第3.1期】预处理系统 WPS 详解:以4.5版本为例
  • [数据结构] 链表
  • 后端使用Spring Boot框架 + 前端VUE 实现滑动模块验证码
  • [Unity] 【VR】【游戏开发】在VR中使用New Input System获取按键值的完整教程
  • 二八(vue2-04)、scoped、data函数、父子通信、props校验、非父子通信(EventBus、provideinject)、v-model进阶
  • 方向导数与梯度
  • 【Linux】多线程
  • OpenCV入门(十八)快速学会OpenCV 17 直线检测
  • 幸福的烦恼:显卡算力太高而pytorch版本太低不支持
  • Power BI利用Python和Sql Server制作实时看板
  • nginx快速入门.跟学B站nginx一小时精讲课程笔记
  • 【百面成神】多线程基础16问,你能坚持到第几问
  • 技术人的管理学-业务管理
  • 扒一扒抖音是如何做线程优化的
  • Markdown常用语法(字体颜色)
  • Python生日蛋糕
  • 网络协议分析期末复习(四)
  • 【vue2】使用vue常见的业务流程与实现思路
  • Docker的可视化界面工具
  • CRC校验算法以及相关实现示例
  • 脱不下孔乙己的长衫,现代的年轻人该怎么办?
  • 百度文心一言正式亮相
  • Linux(网络基础---网络层)
  • 【Python入门第三十五天】Python丨文件打开
  • 论文阅读《Point NeRF:Point-based Neural Radiance Fileds》