动态规划之数字三角形问题_有一个数字三角,从上往下-程序员宅基地

数字三角形问题

Time Limit: 1000MS Memory Limit: 65536KB

Submit Statistic

Problem Description

给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。

Input

输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。

Output

输出数据只有一个整数，表示计算出的最大值。

Example Input

Example Output

Hint

Author

 01
 #include<stdio.h>

 02
 #include<stdlib.h>

 03
 int main()

 04
 {

 05
     int i , j , n;

 06
     int a[110][110];

 07
     scanf("%d",&n);

 08
     for(i=0;i<n;i++)

 09
         for(j=0;j<=i;j++)

 10
     {

 11
         scanf("%d",&a[i][j]);

 12
     }

 13
     for(i=n-2;i>=0;i--)

 14
         for(j=0;j<=i;j++)

 15
     {

 16
         if(a[i+1][j]>a[i+1][j+1])

 17
             a[i][j]+=a[i+1][j];

 18
         else

 19
             a[i][j]+=a[i+1][j+1];

 20
     }

 21
    printf("%d\n",a[0][0]);

 22
     return 0;

 23
 }

本文链接：https://blog.csdn.net/do_you_ac_today/article/details/55251268

智能推荐

杰理AD14N/AD15N---休眠和关机唤醒问题_杰理power off-程序员宅基地

文章浏览阅读1.6k次。杰理JL AD150N、AD153A2、AD153A4、AD156A2、AD158A2、AD159A2、AD142A2、AD145A2、AD146A2.目前的SDK如果不是使用默认配置的PA0引脚做开关机按键，修改了AD按键引脚，则关机后再也唤不醒了，怎么配置？其实SDK用户手册中有介绍：在SDK目录下的DOC文档中可以找到休眠和关机（power down和soft off）的介绍和配置方法，但是当我修改了唤醒IO口以后，发现无法唤醒:于是跟进关机流程的代码，发现不管是power_杰理power off

STM32 使用 SHT2x 温湿度传感器_2x.h-程序员宅基地

文章浏览阅读1.8k次，点赞2次，收藏11次。简介这TM的是个超级坑的通讯过程，虽然符合SPI通讯流程，但要是你直接用SPI通讯会发现完全不是这么回事。这个是在STM32F0系列单片机上使用的范例，可以正常读取温度和湿度，只写了主机模式。database.h 里面没啥东西，可以直接用#include "stm32f0xx.h"代替代码SHT2x.h#ifndef SHT2x_H#define SHT2x_H//-------..._2x.h

docker overlay2占用大量磁盘空间清理_overlay 占用了太多空间-程序员宅基地

文章浏览阅读1.1w次，点赞3次，收藏8次。docker overlay2占用大量磁盘空间清理环境前因正文欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片环境docker版本：Docker version 1.13.1, build 7f2769b/1.13.1linux版本Linux version 3.10.0-693.2.2.el7.x86_64前因线上系统出现问题，磁盘空间不足，导致线上系统不可用，最终定位到了问题原因，这篇文章就是记录清理overlay2目_overlay 占用了太多空间

【Warrior刷题笔记】LC1020.飞地的数量【DFS】详细注释简单易懂-程序员宅基地

文章浏览阅读438次。题目LC1020.飞地的数量解题思路本题可以使用DFS解决。遍历每个格子，如果该格子是陆地，就DFS该陆地所在的岛屿，并计算岛屿面积，并修改格子值为2防止重复遍历。在遍历过程中，只要有一块陆地在边界，这个岛屿就不是飞地，否则就是飞地。计算所有飞地面积之和，返回答案ans。dfs遍历求所有岛屿面积参考LC200.岛屿数量class Solution {private: constexpr static int direction[4][2] = {{-1,0},{1,0},{0,-1},_飞地的数量

二进制，八进制，十进制和十六进制的数值字面量前缀_八进制前缀-程序员宅基地

文章浏览阅读1.3w次，点赞5次，收藏15次。literalJava, C, JS中不同进制数值的字面量前缀：二进制(Binary)字面量前缀：0b或0B。八进制(Octal)：0。十进制(Decimal)字面量无前缀。十六进制(Hex)：0x或0X。codepublic class Test { public static void main(String[] args) { System.out.println(0B1..._八进制前缀

pycharm导入Numpy出现RROR: Could not find a version that satisfies the requirement numpy_error: could not find a version that satisfies the-程序员宅基地

文章浏览阅读1.1k次。现象：出现的原因：pycharm的网络代理出现错误解决方法：打开pycharm:File>>Settings>>Appearance&Behavior>>System setting>>HTTP Proxy,勾选 No Proxy，然后点击OK。然后重启pycharm。解决结果：..._error: could not find a version that satisfies the requirement numpy==1.15.1

随便推点

C++ 学习笔记6--set和multiset、map和multimap(key-value)结构_c++ set 下标-程序员宅基地

文章浏览阅读762次。目录：set初始化、遍历、查找、插入、下标1.1 set的初始化1.2 set的遍历1.3 set的查找1.4 set的插入1.5 set的下标访问1.6 set的修改map初始化、遍历、查找、插入、下标2.1 map的初始化2.2 map的遍历2.3 map的查找2.4 map的插入2.5 map的下标访问1. set初始化、遍历、查找、插入、下标set的特点：1、关键字必须唯一，不能重复2、默认情况下，set中的key会按照升序进行排序3、set的底层实现是_c++ set 下标

客户端与服务器的数据表的同步问题_从服务端获取到的列表同步在客户端的数据库-程序员宅基地

文章浏览阅读4.6k次。图片来源参见水印。文章参考http://a52071453.iteye.com/blog/1978498。美团二面中面试官问了这样的一个问题，在传输有限的情况下，如何保证多个客户端与服务器保持的数据表的一致性？其实解决的方法很简单。先说一下整体的思路：首先由于客户端可能存在很多，而且不可能每个客户端都时时的和服务器保持连接，因此有服务器主导的同步机制是存在问题的。那_从服务端获取到的列表同步在客户端的数据库

解决DVWA“reCAPTCHA key: Missing”-程序员宅基地

文章浏览阅读1.1w次，点赞6次，收藏19次。配置DVWA时出现如下错误：reCAPTCHA key: Missing_recaptcha key: missing

Windows下FFmpeg快速入门sdk下载以及ffmpeg库开发_ffmpeg-full-sdk-3.2.rar-程序员宅基地

文章浏览阅读3.2k次。原文地址：--搞定264 FFMPEG" href="http://blog.sina.com.cn/s/blog_51396f890100o1yf.html" target="_blank">Windows下FFmpeg快速入门sdk下载以及ffmpeg库开发 --搞定264 FFMPEG作者：南无阿弥陀佛Windows下FFmpeg快速入门作者:A.TNG_ffmpeg-full-sdk-3.2.rar

Golang 中Ruquest.FormValue方法_goland formvalue-程序员宅基地

文章浏览阅读3.2k次。Golang中 net/http包下 Request.FormValue 方法可以额获取 url 中? 后面的请求参数例如一package mainimport ( "fmt" "net/http")func main() { http.HandleFunc("/hello", func(writer http.ResponseWriter, request *http.Request) { username := request.FormValue("usern_goland formvalue

博主的简历: 金东升 justin.jin_autovue 21.0.2.4-程序员宅基地

文章浏览阅读1.1k次。金东升Justin.jin 简历简介姓名: 金东升电话/微信: 189 1013 8097职务: Oracle 公司工程与建筑全球事业部(CEGBU)首席顾问Principal Sales Consultant经历从事IT二十多年, 专注于企业级解决方案: 企业项目管理EPPM, 产品生命周期管理PLM1997年~1999年: 海尔集团空调事业部财务科科长19..._autovue 21.0.2.4