一堆以金字塔形状排列的数字，如何找出一条路径，并保证这条从塔尖到底部的路径上的数字之和为最大？
xavierskip · 2014-03-16 21:01:09 +08:00 · 3716 次点击这是一个创建于 3906 天前的主题，其中的信息可能已经有所发展或是发生改变。
如果我描述的还不够清楚，看一下这个挑战的第五关： http://codestar.alloyteam.com/q1/5
 |
1
hncqp 2014-03-16 21:09:57 +08:00
动态规划的典型题目
|
 |
2
66450146 2014-03-16 21:41:41 +08:00
很经典的 DP 题了
|
 |
3
frye 2014-03-16 21:48:24 +08:00 via iPad
腾讯这道题目比较容易做。你从第一个一直往下走，找每行最大的数。如果紧挨着的两个最大的数大小相同的话，那么看这两个数下面紧挨着的数哪个大，以此类推，直到有了唯一的最大数，选择有最大数的那个就可以了。
|
 |
4
jakwings 2014-03-16 21:48:28 +08:00
宝塔数，Google 答案全有，递归解法可以在递归前先判断有没有可能找到得大的数，否则层数加大了就很吃力了。
|
 |
5
lecher 2014-03-16 22:41:36 +08:00
典型的dp，可以用广度搜索空间换时间，开两个数组。一个记录求和，一个记录使用的数字位置。
从顶开始，每个数字依次和上面一层的相邻数字求和，上一层有两个相邻的，保留最大那个，并记录下使用数字的位置。 这么一层一层往下算，算到最后一层，再对最后一层做一个搜索。找出最大的数字。 时间复杂度大概是2n，空间复杂度就是2n |
 |
6
alexrezit 2014-03-17 06:38:14 +08:00 via iPhone
我在 V2EX 上发过通关攻略, 根本没人看.
|
 |
9
muzuiget 2014-03-17 13:18:30 +08:00
看了标题就知道腾讯那个前端游戏了，我自己也用 Python 写了一份。
|
Select Language