首页 > 其他分享 >动态规划--数字三角形

动态规划--数字三角形

时间:2024-01-19 17:35:56浏览次数:29  
标签:200 数字 -- 路径 int 三角形 动态

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

 第一行包括一个整数N,表示有N行,接下来输入数字三角形 输入例子: 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出: 30
#include<bits/stdc++.h>
using namespace std;
int main(){
  int f[200][200];
  int a[200][200];
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
      cin>>a[i][j];
    }
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
      f[i][j]=a[i][j]+max(f[i-1][j-1],f[i-1][j]);
    }
  }
  int m=f[n][1];
  for(int i=1;i<=n;i++){
   if(m<f[n][i]){
     m=f[n][i];
   }
  }
cout<<m;
return 0;
}
 
 关键是: 利用数组进行类似递归的操作,用上一步的最大值来推下一步。

标签:200,数字,--,路径,int,三角形,动态
From: https://www.cnblogs.com/luckyyaoyao/p/17975161

相关文章

  • WiFi协议技术详解概述
    WiFi协议,也称为无线保真技术,是一种允许电子设备通过无线方式在局域网(WLAN)和互联网上进行通信的技术标准。它基于IEEE802.11系列协议,这是一系列由电气和电子工程师协会制定的无线局域网标准。WiFi协议的工作原理主要包括了物理层和数据链路层的协议。在物理层,WiFi协议通过调制解调......
  • cypress实战
     安装环境npmconfigsetregistryhttps://registry.npm.taobao.orgnpminstallcnpmcnpminstallpnpm找到npm的安装目录,加到电脑环境变量里pnpminstallcypress--save-devcypressopen创建一个项目 spec888.cy.js文件/******/(()=>{//webpackBootst......
  • 切面编程
    SpringBoot面向切面编程_springboot切面编程-CSDN博客SpringbootAOP切面编程_springboot切面编程-CSDN博客 切入点签名是什么意思切入点签名是一个包含名字和任意参数的方法签名,用于指定切入点和哪些方法进行匹配 。在AspectJ风格的AOP中,切入点签名采用一......
  • [代码随想录] 第八天
    28.找出字符串中第一个匹配项的下标[https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/]思路:KMP算法,重点在于求NEXT数组。还不能理解..暂时先背下来了。classSolution{publicintstrStr(Stringhaystack,Stringneedle......
  • CVE-2012-1823复现练习
    环境搭建:DockerDesktop开启cd/CVE-2012-1823docker-composeup-d本地访问80端口分析PHP-CGI直接将用户的请求作为了PHP-CGI的参数执行,导致远程代码的执行。先上执行结果PHP的运行模式:CGI通用网关接口,接收网页浏览器的数据发送给web服务器,再把执行结果返回给浏览器参......
  • 二次剩余和 Cipolla 算法
    首先是素数模同余方程的相关理论。下设$p\in$是质数,\(f(x)=\sum_{i=0}^na_ix^i\),\(x\in\Z_p,p\not\mida_n\)。引理1如果\(f(x)\equiv0\pmodp\)具有解\(x_1\simx_k\),且\(k\len\)。则\[f(x)\equivg(x)\prod(x-x_i)\pmodp\]其中\(\degg=n-k,[x^{n-k}]g(x)=a......
  • 【专题】中国可持续金融发展洞察白皮书报告PDF合集分享(附原数据表)
    全文链接:https://tecdat.cn/?p=33318原文出处:拓端数据部落公众号自我国提出双碳目标以来,可持续金融市场发展迅速,呈现蓬勃发展的态势。多年来,致力于中国可持续金融市场的可持续金融战略咨询团队为金融机构提供了相关服务。阅读原文,获取专题报告合集全文,解锁文末358份金融行业相关......
  • python使用selenium操作浏览器的教程
    重复的操作令手工测试苦不堪言,于是自动化测试出现了!作为web应用里最出名的自动化测试工具,selenium让web应用的测试轻松了很多。今天我们就来简单的介绍一下一些简单的selenium浏览器操作。接下来我们就来看看python怎么操作浏览器的吧!1、打开指定的网页地址我们使用selenium进行自......
  • SQL Server 清除一个数据库下所有表数据,保留表结构
    用法:在需要清空数据的数据库创建并执行存储过程,该存储过程并不会影响其他数据库❗请小心使用这些脚本,确保在生产环境之前备份您的数据库。⚠️存储过程:CREATEPROCEDUREClearAllTablesASBEGINDECLARE@TableNameNVARCHAR(255)DECLAREtableCursorCURSORFOR......
  • 如何防止订单二次重复支付?
    1背景用户第一次点击下单操作时,会弹出支付页面待支付。但可能存在用户在支付时发现账户金额不够,后续选择:其他渠道支付(如微信支付转为支付宝支付)或采用不同终端来支付(如由电脑端支付转为app端支付)这时就面临二次支付场景。2方案1由于用户支付的时候的支付页面是html文件或是一个支......