题目67：使用高效算法找到三角形中的最大和。

欧拉计划

Maximum path sum II

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.



That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are altogether! If you could check one trillion routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

题目：

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



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

p067_triangle.txt (14.79 KB, 下载次数: 85)

2015-10-14 15:43 上传

点击文件名下载附件
triangle.txt

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

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

jerryxjr1220

1. 7273
   
2. [Finished in 0.2s]
   
3. 
   
4. lst =[
   
5. ['59'],
   
6. ...,
   
7. ['23','33','44','81','80','92','93','75','94','88','23','61','39','76','22','03','28','94','32','06','49','65','41','34','18','23','08','47','62','60','03','63','33','13','80','52','31','54','73','43','70','26','16','69','57','87','83','31','03','93','70','81','47','95','77','44','29','68','39','51','56','59','63','07','25','70','07','77','43','53','64','03','94','42','95','39','18','01','66','21','16','97','20','50','90','16','70','10','95','69','29','06','25','61','41','26','15','59','63','35']]
   
8. 
   
9. dic = {'00':0,'01':1,'02':2,'03':3,'04':4,'05':5,'06':6,'07':7,'08':8,'09':9}
   
10. lstnew = lst[:]
    
11. for x in range(100):
    
12.         for j in range(x+1):
    
13.                 if lst[x][j] == '00' or lst[x][j] == '01' or lst[x][j] == '02' or lst[x][j] == '03' or lst[x][j] == '04' or lst[x][j] == '05' or lst[x][j] == '06' or lst[x][j] == '07' or lst[x][j] == '08' or lst[x][j] == '09':
    
14.                         lstnew[x][j] = dic[lst[x][j]]
    
15.                 else:
    
16.                         lstnew[x][j] = int(lst[x][j])
    
17. for y in range(1,100):
    
18.         for z in range(y+1):
    
19.                 if z == 0:
    
20.                         lstnew[y][z] += lstnew[y-1][z]
    
21.                 elif z == y:
    
22.                         lstnew[y][z] += lstnew[y-1][z-1]
    
23.                 elif lstnew[y-1][z-1] < lstnew[y-1][z]:
    
24.                         lstnew[y][z] += lstnew[y-1][z]
    
25.                 else:
    
26.                         lstnew[y][z] += lstnew[y-1][z-1]
    
27. print (max(lstnew[99]))
    

复制代码

jerryxjr1220

另外一种，最优化求解的方法（可以适用多路径最优求解）：

1. #coding:utf-8
   
2. #initiate:
   
3. file=open('triangle.txt')
   
4. f=file.read()
   
5. file.close()
   
6. s=f.split('\n')
   
7. triangle = [[]*(i+1) for i in range(100)]
   
8. for i in range(100):
   
9.     triangle[i]=s[i].split()
   
10. for i in range(100):
    
11.     for j in range(i+1):
    
12.         triangle[i][j]=int(triangle[i][j])
    
13. #print (triangle)
    
14. visited = [[False]*(i+1) for i in range(100)]
    
15. dp = [[0]*(i+1) for i in range(100)]
    
16. move = [(1,0),(1,1)]
    
17. checklist = [(0,0)]
    
18. dp[0][0] = 59
    
19. 
    
20. #define method to search the best way:
    
21. def findway(x,y):
    
22.         if not visited[x][y]:
    
23.                 visited[x][y] = True
    
24.                 for m in move:
    
25.                         nx,ny = x+m[0],y+m[1]
    
26.                         if 0<=nx<100 and 0<=ny<=nx:
    
27.                                 dp[nx][ny] = max(dp[x][y]+triangle[nx][ny],dp[nx][ny])
    
28.                                 checklist.append((nx,ny))
    
29. 
    
30. #max9999 is the max price to go:
    
31. max9999 = 0
    
32. 
    
33. #repeat again and again until the max is stable, that's the answer.
    
34. while True:
    
35.         for i in range(len(checklist)):
    
36.                 findway(checklist[i][0],checklist[i][1])
    
37.         if len([(j,k) for j in range(100) for k in range(j) if not visited[j][k]]) == 0:
    
38.                 visited = [[False]*(i+1) for i in range(100)]
    
39.                 checklist = [(0,0)]
    
40.                 if max9999 < max(dp[99]):
    
41.                         max9999 = max(dp[99])
    
42.                 else:
    
43.                         print (max9999)
    
44.                         break

复制代码

芒果加黄桃

1. # encoding:utf-8
   
2. # 计算三角形最长路径
   
3. from time import time
   
4. def readFile():
   
5.     data = []
   
6.     with open('p067_triangle.txt') as f:
   
7.         for line in f:
   
8.             tmp = [int(x) for x in str(line).replace('\n', '').split(sep=' ')]
   
9.             data.append(tmp)
   
10.     return data        
    
11. def euler067():
    
12.     data = readFile()
    
13.     for i in range(len(data) - 2, -1, -1):
    
14.         for j in range(0, len(data[i])):
    
15.             if data[i][j] + data[i + 1][j] > data[i][j] + data[i + 1][j + 1]:
    
16.                 data[i][j] = data[i][j] + data[i + 1][j]
    
17.             else:
    
18.                 data[i][j] = data[i][j] + data[i + 1][j + 1]
    
19.     print(data[0][0])         
    
20. if __name__ == '__main__':
    
21.     start = time()
    
22.     euler067()
    
23.     print('cost %.6f sec' % (time() - start))
    

复制代码

7273
cost 0.017002 sec

刘富国

data67.csv中数据的格式：

1. 59
   
2. 73,41
   
3. 52,40,09
   
4. 26,53,06,34
   
5. 10,51,87,86,81
   
6. 61,95,66,57,25,68
   
7. 90,81,80,38,92,67,73
   
8. 30,28,51,76,81,18,75,44
   
9. ……

复制代码

1. import csv
   
2. 
   
3. nums = []
   
4. with open('data67.csv') as f:
   
5.     reader = csv.reader(f)
   
6.     for row in reader:
   
7.         nums.append(row)
   
8. 
   
9. list1 = []
   
10. i = len(nums)-1
    
11. # 先处理最后一行，选择相邻两个数中大的那个，将其位置、数值放入list1列表中
    
12. for j in range(i):
    
13.     a = nums[i][j]
    
14.     b = nums[i][j+1]
    
15.     if a > b and [i,j,a] not in list1:
    
16.         list1.append([i,j,a])
    
17.     elif b > a and [i,j+1,b] not in list1:
    
18.         list1.append([i,j+1,b])
    
19. 
    
20. # 从倒数第二行开始，依次向上处理
    
21. while i > 0:
    
22.     dict1 = {}
    
23.     i = i-1
    
24.     # 将list1中每个数字的上一行的相邻两个（或一个）数字加到字典dict1中
    
25.     for each in list1:
    
26.         j = each[1]
    
27.         if j == 0:          # 处理每行处于第一列的数字
    
28.             dict1.setdefault((i,j),[]).append(int(nums[i][j])+int(each[2]))
    
29.         elif j == i+1:      # 处理每行处于最后一列的数字
    
30.             dict1.setdefault((i,j-1), []).append(int(nums[i][j-1])+int(each[2]))
    
31.         else:               # 处理中间的数字，由于中间的数字在上一行都会对应两个相邻数字，所以要增加一种情况
    
32.             dict1.setdefault((i, j), []).append(int(nums[i][j])+int(each[2]))
    
33.             dict1.setdefault((i, j - 1), []).append(int(nums[i][j-1])+int(each[2]))
    
34.     # 将字典转换为列表，并选择较大的那个数值
    
35.     list1 = []
    
36.     for each in dict1:
    
37.         list1.append([each[0], each[1], max(dict1[each])])
    
38. print(list1[0][2])

复制代码

7273
0:00:00.015637

fc1735

1. from functools import reduce
   
2. f = open('67.txt')
   
3. t = f.read()
   
4. t = list(map(lambda x: list(map(lambda y: int(y), x.split())),
   
5.       filter(lambda x: len(x) != 0, t.split('\n'))))
   
6. 
   
7. print(max(reduce(lambda x, y: list(map(lambda a, b: a + b, map(max, [0] + x, x + [0]), y)), t)))

复制代码

https://github.com/devinizz/project_euler/blob/master/page02/67.py

debuggerzh

7273

Process returned 0 (0x0)   execution time : 0.049 s
Press any key to continue.
动态规划（dp）经典题，状态转移方程为

                               
登录/注册后可看大图

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<cstdio>
   
4. #include<cstring>
   
5. using namespace std;
   
6. 
   
7. const int M = 100 + 5;
   
8. int a[M][M];
   
9. int opt[M][M];
   
10. 
    
11. int dp(int i,int j){
    
12.   if (opt[i][j] >= 0) return opt[i][j];
    
13.   if (i == 100-1) return opt[i][j] = a[i][j];
    
14.   return opt[i][j] = a[i][j] + max(dp(i+1,j),dp(i+1,j+1));
    
15. }
    
16. 
    
17. int main(){
    
18.   freopen("i.in","r",stdin);
    
19.   memset(opt,-1,sizeof(opt));
    
20. 
    
21.   for (int i = 0;i < 100;i++){
    
22.     for (int j = 0;j <= i;j++){
    
23.       cin >> a[i][j];
    
24.     }
    
25.   }
    
26. 
    
27.   cout << dp(0,0) << endl;
    
28.   return 0;
    
29. }
    

复制代码

永恒的蓝色梦想

C++

1. #include<iostream>
   
2. #include<fstream>
   
3. #include<vector>
   
4. using namespace std;
   
5. using vecus = vector<unsigned short>;
   
6. 
   
7. 
   
8. unsigned int max(const vecus& v) {
   
9.     unsigned int result = 0;
   
10. 
    
11.     for (auto i : v) {
    
12.         if (i > result) {
    
13.             result = i;
    
14.         }
    
15.     }
    
16. 
    
17.     return result;
    
18. }
    
19. 
    
20. 
    
21. void scan(ifstream& file, vecus& v, size_t count) {
    
22.     unsigned short t;
    
23. 
    
24.     for (size_t i = 0; i < count; i++) {
    
25.         file >> t;
    
26.         v[i] = t;
    
27.     }
    
28. }
    
29. 
    
30. 
    
31. void add(const vecus& a, vecus& b) {
    
32.     size_t i;
    
33.     b[0] += a[0];
    
34. 
    
35.     for (i = 1; i < a.size(); i++) {
    
36.         b[i] += max(a[i], a[i - 1]);
    
37.     }
    
38. 
    
39.     b[i] += a[i - 1];
    
40. }
    
41. 
    
42. 
    
43. int main() {
    
44.     ios::sync_with_stdio(false);
    
45. 
    
46.     ifstream file("C:\\Users\\WWW\\Desktop\\0\\p067_triangle.txt");
    
47.     constexpr static size_t N = 100;
    
48.     vecus a(N), b(N);
    
49.     scan(file, b, 1);
    
50. 
    
51. 
    
52.     for (size_t line = 2; line <= N; line++) {
    
53.         swap(a, b);
    
54.         scan(file, b, line);
    
55.         add(a, b);
    
56.     }
    
57. 
    
58. 
    
59.     cout << max(b) << endl;
    
60.     return 0;
    
61. }

复制代码

mathtimes

1. #include <iostream>
   
2. using namespace std;
   
3. #define max(x,y) ((x)>(y)?(x):(y))
   
4. int Array[]={
   
5. #include "p067_triangle.txt"
   
6. };
   
7. #define width 100
   
8. void setmax(int i,int j)
   
9. {
   
10.     if(j == 0)
    
11.         Array[i*(i+1)/2+j] += Array[i*(i-1)/2+j];
    
12.     else if(j == i)
    
13.         Array[i*(i+1)/2+j] += Array[i*(i-1)/2+j-1];
    
14.     else
    
15.         Array[i*(i+1)/2+j] += max(Array[i*(i-1)/2+j],Array[i*(i-1)/2+j-1]);
    
16. }
    
17. int main()
    
18. {
    
19.     for(int i=1;i<width;i++)
    
20.         for(int j=0;j<=i;j++)
    
21.             setmax(i,j);
    
22.     int maxum = 0;
    
23.     for(int i=width*(width-1)/2+0;i<width*(width-1)/2+width;i++)
    
24.         if(maxum<Array[i])
    
25.             maxum = Array[i];
    
26.     cout << maxum;
    
27. }

复制代码

B1tetheDust

1. import time as t
   
2. 
   
3. start = t.perf_counter()
   
4. 
   
5. with open('C:/Users/50598/Desktop/p067_triangle.txt', 'r') as f:
   
6.     file = f.read().splitlines()
   
7.     nums = []
   
8.     for each_row in file:
   
9.         nums.append([int(each_num) for each_num in each_row.split()])
   
10. 
    
11. for i in range(len(nums) - 2, -1, -1):
    
12.     for j in range(i + 1):
    
13.         if nums[i + 1][j] > nums[i + 1][j + 1]:
    
14.             nums[i][j] += nums[i + 1][j]
    
15.         else:
    
16.             nums[i][j] += nums[i + 1][j + 1]
    
17. 
    
18. print(nums[0][0])
    
19. print("It costs %f s" % (t.perf_counter() - start))
    

复制代码

7273
It costs 0.002033 s