V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
xavierskip
V2EX  ›  问与答

一堆以金字塔形状排列的数字,如何找出一条路径,并保证这条从塔尖到底部的路径上的数字之和为最大?

  •  
  •   xavierskip · 2014-03-16 21:01:09 +08:00 · 3715 次点击
    这是一个创建于 3905 天前的主题,其中的信息可能已经有所发展或是发生改变。
    如果我描述的还不够清楚,看一下这个挑战的第五关: http://codestar.alloyteam.com/q1/5
    9 条回复    1970-01-01 08:00:00 +08:00
    hncqp
        1
    hncqp  
       2014-03-16 21:09:57 +08:00
    动态规划的典型题目
    66450146
        2
    66450146  
       2014-03-16 21:41:41 +08:00
    很经典的 DP 题了
    frye
        3
    frye  
       2014-03-16 21:48:24 +08:00 via iPad
    腾讯这道题目比较容易做。你从第一个一直往下走,找每行最大的数。如果紧挨着的两个最大的数大小相同的话,那么看这两个数下面紧挨着的数哪个大,以此类推,直到有了唯一的最大数,选择有最大数的那个就可以了。
    jakwings
        4
    jakwings  
       2014-03-16 21:48:28 +08:00
    宝塔数,Google 答案全有,递归解法可以在递归前先判断有没有可能找到得大的数,否则层数加大了就很吃力了。
    lecher
        5
    lecher  
       2014-03-16 22:41:36 +08:00
    典型的dp,可以用广度搜索空间换时间,开两个数组。一个记录求和,一个记录使用的数字位置。
    从顶开始,每个数字依次和上面一层的相邻数字求和,上一层有两个相邻的,保留最大那个,并记录下使用数字的位置。
    这么一层一层往下算,算到最后一层,再对最后一层做一个搜索。找出最大的数字。
    时间复杂度大概是2n,空间复杂度就是2n
    alexrezit
        6
    alexrezit  
       2014-03-17 06:38:14 +08:00 via iPhone
    我在 V2EX 上发过通关攻略, 根本没人看.
    bengol
        7
    bengol  
       2014-03-17 08:46:52 +08:00
    @alexrezit 不要傲娇 :P
    alexrezit
        8
    alexrezit  
       2014-03-17 08:49:26 +08:00
    @bengol
    真的发过. 0 replies.
    muzuiget
        9
    muzuiget  
       2014-03-17 13:18:30 +08:00
    看了标题就知道腾讯那个前端游戏了,我自己也用 Python 写了一份。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1587 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 17:04 · PVG 01:04 · LAX 09:04 · JFK 12:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.