^O^ 如何用 brute force 遍历路径？

25869

Consider a list of lists in which the first list has one integer and each consecutive list has one more integer then the last. Such a list of lists would look like a triangle. You must write a program that will help Nikola and Stephen look for a route down the pyramid by stepping down and to the left or to the right. Your goal is to make sure this program will find the sturdiest route, that is, the route with the highest possible sum on its way down the pyramid.

Tip: Think of each step down to the left as moving to the same index location or to the right as one index location higher.



Input: A list of lists. Each list contains integers.

Output: An Integer.

Example:

checkio([
    [1],
    [2, 3],
    [3, 3, 1],
    [3, 1, 5, 4],
    [3, 1, 3, 1, 3],
    [2, 2, 2, 2, 2, 2],
    [5, 6, 4, 5, 6, 4, 3]
]) == 23
checkio([
    [1],
    [2, 1],
    [1, 2, 1],
    [1, 2, 1, 1],
    [1, 2, 1, 1, 1],
    [1, 2, 1, 1, 1, 1],
    [1, 2, 1, 1, 1, 1, 9]
]) == 15

上面是一个pyhton 题目，从上到下的和的最大值，上一层的元素只能与下一层相邻的元素配对。

已经找到解决问题的办法，我想知道用brute force 如何解决？
问题：
如何用遍历路径的办法解决这个问题？ 即从上到下所有的可能
或者说如何遍历所有的路径，这个我不会写。

多谢指教！


Mickey Stone

laike9m

标准解法是动态规划吧。不明白遍历哪里难写？

25869

回复 2# laike9m

多谢大侠回复，刚开始学编程，两个星期，还没看到算法那块儿呢，所以摸不着头绪
正在google 'dp'

只要知道如何列出所有的路径，就可以了，我自己画了一下图，看着有点像二叉树，研究中

至于原题的求最大值，那个问题我已经解决了。