小练习：20170403 使用高效算法找到三角形中的最大和

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

                               
登录/注册后可看大图

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成，即4.10 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

----回帖需写明解题思路，鼓励在程序中加上注释



题目：

从以下三角形的顶端开始，向下一行的相邻数字移动，从顶端到底端的最大总和是 23 。

                               
登录/注册后可看大图

也就是 3 + 7 + 4 + 9 = 23。

                               
登录/注册后可看大图

p067_triangle.txt (14.79 KB, (右键另存为)是一个文本文件，包含了一个一百行的三角形，找出这个三角形中从顶到底的最大和。

注意：这是题目 18 的更难的一个版本。穷举每一种可能的路径是不可行的，因为一共有

                               
登录/注册后可看大图

条可能的路径。就算每秒钟能处理

                               
登录/注册后可看大图

条路径，也需要 200 亿年来处理完所有的路径。存在一个高效的方法来处理这道题。

jerryxjr1220

这题是比较典型的动态规划算法吧，每次相加都是比较下一行的邻接数，哪个大加给哪个。

1. with open('p067_triangle.txt') as f:
   
2.     lines = f.readlines()
   
3. triangle = []
   
4. for i in range(100):
   
5.     triangle.append([int(each) for each in lines[i].split() if each or each == '00'])
   
6. for i in range(99):
   
7.     for j in range(i+2):
   
8.         if j == i+1:
   
9.             triangle[i+1][j] += triangle[i][i]
   
10.         else:
    
11.             triangle[i+1][j] += max(triangle[i][j], triangle[i][j-1])
    
12. print max(triangle[-1])

复制代码

答案：7273

gopythoner

想了一下，对于我这种只会循环的人来说，不可能解答
沙发不要了，收个板凳，坐等大佬来解题

余欲渔

正的慢就反着算,算掉一层是一层,

1. 文件=open('lujing.txt')
   
2. ta=[]
   
3. for i in 文件:   
   
4.     临时=[(int(i[j:j+2]) ) for j in range(0,len(i),3)]
   
5.     ta.append(临时)
   
6. 文件.close()
   
7. 
   
8. for i in range(1,100):
   
9.     ta[-i-1] = [max(ta[-i-1][j]+ta[-i][j],ta[-i-1][j]+ta[-i][j+1]) for j in range(len(ta[-i-1]))]
   
10. 
    
11. print('最大总和为：',ta[0][0])

复制代码

lovesword

1. #!/usr/bin/env python
   
2. # coding=utf-8
   
3. #python 2.7
   
4. import time
   
5. start = time.time()
   
6. max_ = 0
   
7. tmp={}
   
8. def move_l_r(i,idx):
   
9.     global max_
   
10.     if i==0:
    
11.         tmp[(0,0)]=list_[i][0]
    
12.     else:
    
13.         if idx==0:
    
14.             tmp[(i,idx)]=tmp[(i-1,idx)]+list_[i][idx]
    
15.         elif idx == len(list_[i])-1:
    
16.             tmp[(i,idx)]=tmp[(i-1,idx-1)]+list_[i][idx]
    
17.         else:
    
18.             tmp[(i,idx)]=max(tmp[(i-1,idx)],tmp[(i-1,idx-1)])+list_[i][idx]
    
19.     if tmp[(i,idx)]>max_:
    
20.         max_=tmp[(i,idx)]
    
21.     return max_
    
22. file_ = open('p067_triangle.txt')
    
23. list_ = [map(int,i.split()  ) for i in file_.readlines()]
    
24. file_.close()
    
25. for idx_i,i in enumerate(list_):
    
26.     for idx_j,j in enumerate(i):
    
27.         max_=move_l_r(idx_i,idx_j)
    
28. print 'sec:',time.time()-start
    
29. print 'res:',max_
    
30. 
    
31. #-------------------------
    
32. sec: 0.00722813606262
    
33. res: 7273

复制代码

达锅

楼主，开放答案啊。。。