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 写了一份。
|