动态规划之数字三角形问题_鹿海园的博客-程序员秘密

数字三角形问题

Time Limit: 1000MS  Memory Limit: 65536KB
Submit  Statistic

Problem Description

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

Input

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

Output

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

Example Input

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Example Output

30

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 }

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/do_you_ac_today/article/details/55251268

智能推荐

Windows下安装PHPUnit详解_chuofei7203的博客-程序员秘密

Windows下安装PHPUnit详解 最近研究php的单元测试功能，在centos下和widows下安装了phpunit 首先要保证你装的php中安装了pear linux下输入命令pear 回车可看一下是否安装了 windows下可以用dos进入到php的安装目...

Lua中调用C/C++函数_lua调用c++函数_foreverhuylee的博客-程序员秘密

Lua中调用C/C++函数　　上次偶说到从C/C++中调用Lua的函数, 然后就有朋友问从Lua中如何调用C/C++的函数, 所以偶们这次就来说说这个问题. 首先偶们会在C++中建立一个函数, 然后告知Lua有这个函数, 最后再执行它. 另外, 由于函数不是在Lua中定义的, 所以无法确定函数的正确性, 可能在调用过程中会出错, 因此偶们还会说说Lua出错处理的问题.　　2.L

JAVA逆序输出整型数字_java逆序输出数字_星汉空兮的博客-程序员秘密

1、功能实现：输入：一个整型数字，可以是负数、0、正数输出：将输入的数逆序输出，如果原数末尾有0，则删除，直至逆序输出的数的第一位不是02、程序如下：import java.util.Scanner;public class Main { static String ss=""; public static void main(String[] args) { Scann...

ajax 入参为list_ajax传递给后台数组参数方式_weixin_39588419的博客-程序员秘密

出自：http://blog.csdn.net/lingxyd_0/article/details/10428785在项目上用到了批量删除与批量更改状态，前台使用了EasyUI的DataGrid，用到了批量更改数据状态功能。在前台可以获取每条数据的ID，但是如何通过数组方式传递给后台？通过昨晚的各种方式的调试，终于得出了答案！ 在此作为备忘。目前有两种方式可行：方式一前台代码：// 方式一var ...

POE交换机供电时，网线如何连接？_poe供电网线一分二接法图_普天信科的博客-程序员秘密

有关如何连接的难以解决的问题 ，其实并非是很难 ，可以RJ45网线插口可以来给适用于POE供电的专用设备供电 。　　你要是问RJ45 网线水晶头是那几根来供电的话 ，回答如下所述所示 ：1236（白橙.橙.绿白.绿）跑数据信息(现阶段五类网线接线方法实际上仅用这四根 )，45 （蓝.白绿）开关电源 正级 78 （白棕 .棕）开关电源负级。 POE供电系统软件是运用双绞线(也就是大家通称的网线 )来开展通讯数据信号与电力传输 的，一般来说是根据 CAT .5 之上 (包含 )的...

用MATLAB进行区间估计_matlab对样本的方差进行区间估计_sereasuesue的博客-程序员秘密

数据正态总体分布normfit()命令来完成对参数的点估计和区间估计。此命令以alpha为显著性水平，在数据X下，对参数进行估计（alpha缺省时设定为0.05）[muhat,sigmahat,muci,sigmaci]= normfit(X,alpha)muhat是正态分布的均值的点估计值sigmahat是标准差的点估计muci是均值的区间估计sigmaci是标准差的区间估计y=[1050,1100,1080,1120,1200,1250,1040,1130,1300,1200]..

随便推点

Java面试很难？啃完阿里老哥这套Java架构速成笔记，我都能拿30K_程序员黑哥的博客-程序员秘密

最近有不少小伙伴在后台留言，说 Java 的面试越来越难了，尤其是技术面，考察得越来越细，越来越底层。作为一名程序员，技术面试是不可避免的一个环节，一般技术面试官都会通过自己的方式去考察程序员的技术功底与基础理论知识。如果你参加过一些面试，肯定会遇到一些这样的问题：项目框架，Spring、Mybatis 等框架实现原理是否熟悉？消息中间件，负载均衡、RPC 框架等技术是否有接触过？MySQL 分库分表是否做过?分布式架构设计，Redis 分布式锁是否有涉及?…(此处省略 1W 字)很多时.

兄弟连新年联欢会_u011886490的博客-程序员秘密

2013年1月5日,天气晴,微风.事件:兄弟连新年联欢会兄弟连官方收看地址: http://www.lampbrother.net/happy2013.html觉得这个域名不能表达参加联欢会后的愉悦程度,应该是high2013.html！完全被现场老师和同学的表现给震了，有所耳闻，明哥和高胖的猥琐程度，今天开眼了，引用明哥一句话“这帮老小子” （PS：引用明哥的原创，这

echarts画散点图(数据处理用python，数据展示用echarts)第一篇_echarts python 散点图_金融小白数据分析之路的博客-程序员秘密

文档使用手册https://echarts.apache.org/zh/index.html&lt;!DOCTYPE html&gt;&lt;html&gt;&lt;head&gt; &lt;meta charset="utf-8"&gt; &lt;title&gt;美国枕套top20&lt;/title&gt; &lt;!-- 引入 echarts.js --&gt; &lt;script src="https://cdn.staticfile.org/ech

思科模拟器动态路由ospf_ZDYYY.的博客-程序员秘密

网络拓扑图：Router0配置：Router1配置：Multilayer Switch0配置：Switch0配置：Switch1配置：主机PC0配置：202.199.1.2255.255.255.0202.199.1.1主机PC1配置：202.199.2.2255.255.255.0202.199.2.1主机PC2配置：202.199.3.2255....

vue结合elementUI实现tag多标签页_element ui 标签页_woowen！的博客-程序员秘密

vue结合elementUI实现tag多标签页点击左侧菜单栏，会打开一个相应的tag标签页 点击tag标签可以在不同tag之间切换如图：以上图片的布局如下：&lt;el-container&gt; &lt;BaseAside /&gt; &lt;el-main&gt; &lt;el-header&gt; &lt;AppTag /&gt; &lt;/el-header&gt; &lt;el-mai

pkill -9_夜跑者的博客-程序员秘密

这个命令不错，直接杀死进程，不用找进程ID了。busybox pkill -9 xxx        把这条命令放到secureRT button Bar 里面 。  鼠标轻轻一点就杀死进程了。。。。

推荐文章

热门文章

相关标签