Golden Pyramid
Our Robo-Trio need to train for future journeys and treasure hunts. Stephan has built a special flat model of a pyramid. Now the robots can train for speed gold running. They start at the top of the pyramid and must collect gold in each room, choose to take the left or right path and continue down to the next level. To optimise their gold runs, Stephan need to know the maximum amount of gold that can be collected in one run.
Consider a tuple of tuples in which the first tuple has one integer and each consecutive tuple has one more integer then the last. Such a tuple of tuples would look like a triangle. You should write a program that will help Stephan find the highest possible sum on the most profitable route down the pyramid. All routes down the pyramid involve stepping down and to the left or down and to the right.
Tips: Think of each step down to the left as moving to the same index location or to the right as one index location higher. Be very careful if you plan to use recursion here.
Input: A pyramid as a tuple of tuples. Each tuple contains integers.
Output: The maximum possible sum as an integer.
题目大义: 数字金字塔, 找出从顶部到底部, 路径的最大和(即这条路径上的数字相加的和为最大)
经典的DP问题D[i][j] = max(D[i - 1][j], D[i - 1][j - 1]) + Pyramid[i][j]
def count_gold(pyramid):
"""
Return max possible sum in a path from top to bottom
""" step = len(pyramid) sub_sum = [[0 for row in range(0, step)] for col in range(0, step)] sub_sum[0][0] = pyramid[0][0] for i in range(0, step):
for j in range(0, i + 1):
if i >= 1:
if j >= 1 and sub_sum[i - 1][j - 1] + pyramid[i][j] > sub_sum[i][j]:
sub_sum[i][j] = sub_sum[i - 1][j - 1] + pyramid[i][j] if sub_sum[i - 1][j] + pyramid[i][j] > sub_sum[i][j]:
sub_sum[i][j] = sub_sum[i - 1][j] + pyramid[i][j] max_sum = 0
for each in sub_sum[step - 1][:step]:
if each > max_sum:
max_sum = each #replace this for solution
return max_sum
其实这份代码类似C语言的实现
观摩zero_loss的python实现
def count_gold(pyramid):
py = [list(i) for i in pyramid]
for i in reversed(range(len(py)-1)):
for j in range(i+1):
py[i][j] +=(max(py[i+1][j], py[i+1][j+1])) return py[0][0]
这个实现是从下往上走, 非常简洁;
Golden Pyramid的更多相关文章
-
[Math]PHI, the golden ratio
PHI, the golden ratio 黄金分割比 转载自 http://paulbourke.net/miscellaneous/miscnumbers/ 1. Definition 将一个线段 ...
-
CF 676B Pyramid of Glasses[模拟]
B. Pyramid of Glasses time limit per test 1 second memory limit per test 256 megabytes input standar ...
-
Spatial pyramid pooling (SPP)-net (空间金字塔池化)笔记(转)
在学习r-cnn系列时,一直看到SPP-net的身影,许多有疑问的地方在这篇论文里找到了答案. 论文:Spatial Pyramid Pooling in Deep Convolutional Net ...
-
论文笔记之:Deep Generative Image Models using a Laplacian Pyramid of Adversarial Networks
Deep Generative Image Models using a Laplacian Pyramid of Adversarial Networks NIPS 2015 摘要:本文提出一种 ...
-
Why The Golden Age Of Machine Learning is Just Beginning
Why The Golden Age Of Machine Learning is Just Beginning Even though the buzz around neural networks ...
-
C Golden gun的巧克力
Time Limit:1000MS Memory Limit:65535K 题型: 编程题 语言: 无限制 描述 众所周知,13级有尊大神Golden gun,人称根叔,简称金枪!众立志进校队的 ...
-
10 Golden Rules of Project Risk Management
The benefits of risk management in projects are huge. You can gain a lot of money if you deal with u ...
-
The golden ratio: 1.618
http://www.chinaz.com/design/2015/1109/467968_2.shtml The golden ratio: 1.618 a/b=b/(a+b) The Fibona ...
-
codeforces 676B B. Pyramid of Glasses(模拟)
题目链接: B. Pyramid of Glasses time limit per test 1 second memory limit per test 256 megabytes input s ...
随机推荐
-
mysql5.7安装配置
sonar要求mysql5.6版本,所以安装一下最新的mysql5.7 相对路径配置一直存在问题,所以采用绝对路径配置,本次配置的基础路径是: D:\sonar\mysql-5.7.17-winx64 ...
-
AIX下tar解包问题
今天,在AIX下安装tomcat,上传的版本是apache-tomcat-6.0.41.tar.gz,但用tar解压时出现以下问题: # tar xvf apache-tomcat-6.0.41.ta ...
-
iOS:详细的正则表达式
1.简介: 在项目中,正则的使用是很普遍的,例如登录账号和密码(手机号.邮箱等).用到的方法就是谓词对象过滤:NSPredicate. 2.什么是正则表达式: 正则表达式,又称正规表示法,是对字符串操 ...
-
jquery 实现 点击按钮后倒计时效果,多用于实现发送手机验证码、邮箱验证码
原文链接:http://www.cnblogs.com/steed-zgf/archive/2012/02/03/2336984.html <!DOCTYPE html PUBLIC " ...
-
ASP.NET MVC在服务端把异步上传的图片裁剪成不同尺寸分别保存,并设置上传目录的尺寸限制
我曾经试过使用JSAjaxFileUploader插件来把文件.照片以异步的方式上传,就像"MVC文件图片ajax上传轻量级解决方案,使用客户端JSAjaxFileUploader插件01- ...
-
15个最好的Bootstrap设计工具推荐
摘要:Bootstrap不单单是一个框架,更确切的说,它改变了整个游戏规则.该框架使得许多应用和网站的设计开发变得简便许多,而且它将大量的HTML框架普及成了产品. Bootstrap是由前Twitt ...
-
JSP简单练习-数组应用实例
<%@ page contentType="text/html; charset=gb2312" %> <html> <body> <% ...
-
【Android开发日记】第一个任务Android Service!Service靴+重力感应器+弹出窗口+保持执行
前言: 近期在写一个小程序,需求是手机摇一摇就弹窗出来.第一次使用了Service,学习了两天,实现了Service弹窗,开机启动,Service启动和销毁,Service保持一直执行. 满足了自己的 ...
-
angular $parse $eval parse VS eval
$parse angular中重要指令介绍($eval,$parse和$compile) Advanced Angular: $parse $parse ---------------------- ...
-
spring4笔记----报错publicid systemid之间要有空格的解决方法
<?xml version="1.0" encoding="GBK"?> <beans xmlns:xsi="http://www. ...