成长每一点---题库11---4 Kuy（难度---三角形最大和）

Stubborn

欧拉计划18题
欧拉计划67题


这是题目 18 的更难的一个版本。穷举每一种可能的路径是不可行的，因为一共有2**99  条可能的路径。就算每秒钟能处理 10**12 条路径，也需要 200 亿年来处理完所有的路径。存在一个高效的方法来处理这道题。

你的任务是编写一个函数longestSlideDown（在ruby中:) longest_slide_down，它将金字塔表示作为参数并返回其“ 最长 ”向下滑动'。例如

longestSlideDown([[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]])
# => 23

算法  功能编程  声明性编程  高阶函数  功能控制流  基本语言功能   基本面

Stubborn

1. def longest_slide_down(pyramid):
   
2.     def findway(x, y):
   
3.         if not visited[x][y]:
   
4.             visited[x][y] = True
   
5.             for m in move:
   
6.                 nx, ny = x + m[0], y + m[1]
   
7.                 if 0 <= nx < len(pyramid) and 0 <= ny <= nx:
   
8.                     dp[nx][ny] = max(dp[x][y] + pyramid[nx][ny], dp[nx][ny])
   
9.                     checklist.append((nx, ny))
   
10. 
    
11.     visited = [[False] * (i + 1) for i in range(len(pyramid))]
    
12.     dp = [[0] * (i + 1) for i in range(len(pyramid))]
    
13.     move = [(1, 0), (1, 1)]
    
14.     checklist = [(0, 0)]
    
15.     dp[0][0] = pyramid[0][0]
    
16. 
    
17.     max = 0
    
18. 
    
19.     while True:
    
20.         for i in range(len(checklist)):
    
21.             findway(checklist[i][0], checklist[i][1])
    
22.         if len([(j, k) for j in range(len(pyramid)) for k in range(j) if not visited[j][k]]) == 0:
    
23.             visited = [[False] * (i + 1) for i in range(len(pyramid))]
    
24.             checklist = [(0, 0)]
    
25.             if max < max(dp[len(pyramid)-1]):
    
26.                 max = max(dp[len(pyramid)-1])
    
27.             else:
    
28.                 break
    
29.     return max

复制代码

1. def longest_slide_down(p):
   
2.     res = p.pop()
   
3.     while p:
   
4.         tmp = p.pop()
   
5.         res = [tmp[i] + max(res[i],res[i+1])  for i in range(len(tmp))]  #把tmp的每个值。加上tmp值对应上方res较大的一个值。
   
6.     return res.pop()
   
7. #代码分析=========保持res为最后一列，tmp为倒数第二列
   
8. aa=[[4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23],
   
9.    [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
   
10.    [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
    
11.    [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
    
12.    [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
    
13.    [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
    
14.    [41, 41, 26, 56, 83, 40, 80, 70, 33],
    
15.    [99, 65, 4, 28, 6, 16, 70, 92],
    
16.    [88, 2, 77, 73, 7, 63, 67],
    
17.    [19, 1, 23, 75, 3, 34],
    
18.    [20, 4, 82, 47, 65],
    
19.    [18, 35, 87, 10],
    
20.    [17, 47, 82],
    
21.    [95, 64],
    
22.    [75]]

复制代码

1. def longest_slide_down(pyramid):
   
2.         "从后面开始处理"
   
3.     for i in range(len(pyramid)-2,-1,-1):  #i为13到0
   
4.         for j in range(i+1):  #第一次0-13 每循环一次-1
   
5.             pyramid[i][j] += max([pyramid[i+1][j],pyramid[i+1][j+1]])
   
6.                 #  倒数第二列第j个值    +=   max（最后一列，j对应的二个值）
   
7.     return pyramid[0][0]

复制代码

1. class Tree(object):
   
2.     value = summ = None
   
3.     left = right = None
   
4.    
   
5.     def __init__(self, value):
   
6.         self.value = value
   
7. 
   
8. 
   
9. def iter_pairs(level):
   
10.     it = iter(level)
    
11.     a, b = Tree(next(it)), Tree(next(it))
    
12.     while b.value is not None:
    
13.         yield a, b
    
14.         a, b = b, Tree(next(it, None))
    
15. 
    
16. 
    
17. def build_tree(pyramid):
    
18.     it = iter(pyramid)
    
19.     root = Tree(next(iter(next(it))))
    
20.     prev_level = iter([root])
    
21.     for level in it:
    
22.         tree_level = []
    
23.         parent = next(prev_level)
    
24.         
    
25.         for left_tree, right_tree in iter_pairs(level):
    
26.             tree_level.append(left_tree)
    
27. 
    
28.             parent.left = left_tree
    
29.             parent.right = right_tree
    
30.             parent = next(prev_level, None)
    
31.             
    
32.         tree_level.append(right_tree)
    
33.         prev_level = iter(tree_level)
    
34. 
    
35.     return root
    
36. 
    
37. 
    
38. def calc_max_sums(root):
    
39.     if root is None:
    
40.         return 0
    
41. 
    
42.     if root.summ is not None:
    
43.         return root.summ
    
44. 
    
45.     root.summ = root.value + max(calc_max_sums(root.left), calc_max_sums(root.right))
    
46.     return root.summ
    
47. 
    
48. 
    
49. def find_max_slide(root):
    
50.     if root is None:
    
51.         return 0
    
52. 
    
53.     if not (root.left and root.right):
    
54.         return root.value
    
55. 
    
56.     if root.left.summ >= root.right.summ:
    
57.         return root.value + find_max_slide(root.left)
    
58.    
    
59.     if root.left.summ < root.right.summ:
    
60.         return root.value + find_max_slide(root.right)
    
61. 
    
62. 
    
63. def longest_slide_down(pyramid):
    
64.     tree = build_tree(pyramid)
    
65.     calc_max_sums(tree)
    
66.     return find_max_slide(tree)

复制代码

1. def longest_slide_down(tri):
   
2.   while len(tri) > 1:
   
3.     t0 = tri.pop()
   
4.     t1 = tri.pop()
   
5.     tri.append([max(t0[i], t0[i+1]) + t for i,t in enumerate(t1)])
   
6.   return tri[0][0]

复制代码

1. from operator import add
   
2. def longest_slide_down(pyramid):
   
3.     return reduce(lambda x, y: map(add, map(max, x[1:], x[:-1]), y), reversed(pyramid))[0]

复制代码

1. from itertools import izip
   
2. 
   
3. def longest_slide_down(pyramid):
   
4.     sums = pyramid[-1]
   
5.     for row in pyramid[-2::-1]:
   
6.         sums = [a + max(b, c) for (a, b, c) in izip(row, sums, sums[1:])]
   
7.     return sums[0]

复制代码

1. def longest_slide_down(p):
   
2.     p[-1] = map(max, zip(p[-1][:-1], p[-1][1:]))
   
3.     p[-2] = map(sum, zip(p[-1], p[-2]))
   
4.     return longest_slide_down(p[:-1]) if len(p) > 2 else p[0][0]

复制代码

1. def longest_slide_down(pyramid):
   
2.     return reduce(lambda prev, cur: map(lambda (i, el): el + max(prev[i], prev[i+1]), enumerate(cur)), reversed(pyramid))[0]

复制代码

1. def longest_slide_down(a):
   
2.   return longest_slide_down(a[:-2]+[[a[-2][i]+max(a[-1][i],a[-1][i+1]) for i in xrange(len(a[-2]))]]) if len(a)>1 else a[0][0]

复制代码

1. longest_slide_down = lambda l:reduce(lambda x,y:[max([x[i],x[i+1]])+y[i] for i in range(len(y))],l[::-1])[0]
   

复制代码

Stubborn

@塔利班 @heidern0612 @Ice_in_left 人生苦短我用python,一行代码，最为致命，正所谓，推导虐我千百遍，只能待你如初恋，最后三个代码，推导过不去，代码直接copy过来的，可以帮忙看看哪里错了吗？ 题目做多了，总觉得这个题目是不是一样推导就过去了 有推导训练集吗。班利塔大神，@塔利班 大哥@heidern0612  可以帮忙讲下倒数两个吗 ，一个推导，一个递归

塔利班

多了看着就乱

注册列表

这个题目在哪里呢？

Stubborn

注册列表 发表于 2019-1-19 23:08
这个题目在哪里呢？

有两个链接，欧拉计划18题，和67题，这属于67题。可以先看18题，练习下。

注册列表

Stubborn 发表于 2019-1-19 23:15
有两个链接，欧拉计划18题，和67题，这属于67题。可以先看18题，练习下。

67和18不太一样，第一个可以枚举第二个得动归啊

Stubborn

注册列表 发表于 2019-1-20 17:01
67和18不太一样，第一个可以枚举第二个得动归啊

6行代码可以搞定，不用枚举

注册列表

Stubborn 发表于 2019-1-20 17:05
6行代码可以搞定，不用枚举

我从幼儿园开始就缺乏解决问题的方法，等我学学再来。。。。

Stubborn

注册列表 发表于 2019-1-20 17:10
我从幼儿园开始就缺乏解决问题的方法，等我学学再来。。。。

从后面算起比较快。

注册列表

帮我测试这段代码
lista=[]<输入列表>
ub =len(lista)
list1=[]
list2=[]
for i in range(ub-1,0,-1):
    for j in range(0,i):
        list1.append(max(lista[i-1][j]+lista[i][j],lista[i-1][j]+lista[i][j+1]))
    del lista[i]
    del lista[i-1]
    lista.append(list1)
    list1=[]
print(lista[0][0])


现学现卖不知道咋样。。。。例子的两个都没问题

Stubborn

注册列表 发表于 2019-1-20 20:59
帮我测试这段代码
lista=[]
ub =len(lista)

做我最新的那个，==我跟新下我也准备做

注册列表

Stubborn 发表于 2019-1-20 21:13
做我最新的那个，==我跟新下我也准备做

我特意做了个西里古怪的。。结果忘记打return结果函数判断一部分输不出来

秋木叶

老哥稳！！