题目18：找出从三角形顶端走到底端的最大和

欧拉计划

Maximum path sum I

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 of the triangle below:



NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

题目：

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



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

找出从以下三角形的顶端走到底端的最大总和：

huomqh

def f(r,c,sss,link):
    if r==14:
        y=[sss,link]
        k.append(y)
        return 1
    else:
        f(r+1,c,sss+a[r+1][c],link+"+"+str(c))
        f(r+1,c+1,sss+a[r+1][c+1],link+"+"+str(c+1))
    
        


a=[[75],[95,64],[17,47,82],[18,35,87,10],[20,4,82,47,65],[19,1,23,75,3,34],[88,2,77,73,7,63,67],[99,65,4,28,6,16,70,92],[41,41,26,56,83,40,80,70,33],[41,48,72,33,47,32,37,16,94,29],[53,71,44,65,25,43,91,52,97,51,14],[70,11,33,28,77,73,17,78,39,68,17,57],[91,71,52,38,17,14,91,43,58,50,27,29,48],[63,66,4,68,89,53,67,30,73,16,69,87,40,31],[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]
k=[]
result=[]
f(0,0,a[0][0],'0')
m=0
for i in k:
   if i[0]>m:
       m=i[0]
       result=i[:]
print (result[0])
b=result[1].split("+")
l=str(a[0][0])
for z in range(1,len(b)):
    l=l+"+"+str(a[z][int(b[z])])
print(l)
    

这次应该对了
1074
75+64+82+87+82+75+73+28+83+32+91+78+58+73+93

huomqh

随便写写的，可读性很差，大家见谅。
附一张分布图吧

                               
登录/注册后可看大图

Plusenxue

a=[[4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23],
   [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
   [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
   [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
   [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
   [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
   [41, 41, 26, 56, 83, 40, 80, 70, 33],
   [99, 65, 4, 28, 6, 16, 70, 92],
   [88, 2, 77, 73, 7, 63, 67],
   [19, 1, 23, 75, 3, 34],
   [20, 4, 82, 47, 65],
   [18, 35, 87, 10],
   [17, 47, 82],
   [95, 64],
   [75]]
for i in range(1,15):
    for j in range(15-i):
        if a[i-1][j] < a[i-1][j+1]:
            a[i][j] = a[i][j]+a[i-1][j+1]
        else:
            a[i][j] = a[i][j]+a[i-1][j]

print(a[14][0])

迷雾少年

1074 应该是吧。。

#include <iostream>
using namespace std;
int myMaxNumber = 0;
/* 数组线性保存 */
int myArry[]={
        75,
        95,64,
        17,47,82,
        18,35,87,10,
        20,04,82,47,65,
        19,01,23,75,03,34,
        88,02,77,73,07,63,67,
        99,65,04,28,06,16,70,92,
        41,41,26,56,83,40,80,70,33,
        41,48,72,33,47,32,37,16,94,29,
        53,71,44,65,25,43,91,52,97,51,14,
        70,11,33,28,77,73,17,78,39,68,17,57,
        91,71,52,38,17,14,91,43,58,50,27,29,48,
        63,66,04,68,89,53,67,30,73,16,69,87,40,31,
        04,62,98,27,23,9,70,98,73,93,38,53,60,04,23

        };
int myArry2[]={3,7,4,2,4,6,8,5,9,3};

/* 获取第h行第1个数 */
/*  递归关系 f(1) = 1  f(x) = f(x-1) + 1 */
int getNumber(int h)
{
        int n = 0;
        if(1==h)
        {
                return 1;
        }
         n = getNumber(h-1);
        return n+(h-1);
}
int getNum(int h,int l)
{
        return myArry[getNumber(h)+l-2];
}
int getMaxNum(int l,int h,int result)
{
        int j,k;
        j = l;
        k = l + 1;
        //如果到达最底层  算出结果 
        if( 15 == h )
        {
                int a = result + getNum(h,l);
                if( myMaxNumber < a)
                {
                        myMaxNumber = a;
                }
                return a;
        }

        /* 接着上一层的开始  */
        getMaxNum(j,h+1,result+getNum(h,l));
        getMaxNum(k,h+1,result+getNum(h,l));
}
int main(void)
{
        getMaxNum(1,1,0);
        std::cout<<myMaxNumber;
        return 0;
}

渡风

此代码使用matlab编程
Problem18所用时间为2.0008秒
Problem18的答案为1074

%题目18：找出从三角形顶端走到底端的最大和
%本质上是二叉树
function Output=Problem18(Input)
 tic
if nargin==0
  Input=[75,zeros(1,14);...
         95,64,zeros(1,13);...
         17,47,82,zeros(1,12);...
         18,35,87,10,zeros(1,11);...
         20,04,82,47,65,zeros(1,10);...
         19,01,23,75,03,34,zeros(1,9);...
         88,02,77,73,07,63,67,zeros(1,8);...
         99,65,04,28,06,16,70,92,zeros(1,7);...
         41,41,26,56,83,40,80,70,33,zeros(1,6);...
         41,48,72,33,47,32,37,16,94,29,zeros(1,5);...
         53,71,44,65,25,43,91,52,97,51,14,zeros(1,4);...
         70,11,33,28,77,73,17,78,39,68,17,57,zeros(1,3);...
         91,71,52,38,17,14,91,43,58,50,27,29,48,zeros(1,2);...
         63,66,04,68,89,53,67,30,73,16,69,87,40,31,zeros(1,1);...
         04,62,98,27,23,9,70,98,73,93,38,53,60,04,23];
end
Pro=2^(length(Input(1,:))-1);%有多少种可能
A=Input;
L=length(Input(1,:))-1;
Result=0;
for ii=1:Pro
    V=Get2bit(ii-1,L);%V=Vector,一个数二进制表示的向量
    Sum=A(1,1);
    for jj=1:L
        Sum=Sum+A(jj+1,1+sum(V(1:jj)));
    end
    if Sum>Result
        Result=Sum;
    end
end
toc
Output=Result;
disp('此代码使用matlab编程')
disp(['Problem18所用时间为',num2str(toc),'秒'])
disp(['Problem18的答案为',num2str(Output)])
end
%% 子程序
%输入一个数Input，得到其二进制表示，L为期长度
function Output=Get2bit(Input,L)
if nargin==0
L=14;
Input=56;
end
Temp=Input;
Rank=[];
while (Temp>=1)
    Rank_Temp=[Rank,mod(Temp,2)];
    Rank=Rank_Temp;
    Temp=floor(Temp/2);
end
if length(Rank)<L
    Output=[Rank,zeros(1,L-length(Rank))];
else
    Output=Rank;
end
end

永丨恒

temp = '''75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''

temp = [i.split(' ') for i in temp.split('\n')]

for i in range(len(temp) - 2, -1, -1):
    for j in range(len(temp[i])):
        temp[i][j] = max(int(temp[i][j]) + int(temp[i + 1][j]), int(temp[i][j]) + int(temp[i + 1][j + 1]))
    print temp[i]

从下往上算比较高效，此代码适用于第67题，只要把上面的数字替换即可。

zzzgod

#include <iostream>
#include <cmath>
using namespace std;
int max1=0;
int map[16][16]={
        {00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00},
        {00,75,00,00,00,00,00,00,00,00,00,00,00,00,00,00},
        {00,95,64,00,00,00,00,00,00,00,00,00,00,00,00,00},
        {00,17,47,82,00,00,00,00,00,00,00,00,00,00,00,00},
        {00,18,35,87,10,00,00,00,00,00,00,00,00,00,00,00},
        {00,20, 4,82,47,65,00,00,00,00,00,00,00,00,00,00},
        {00,19, 1,23,75, 3,34,00,00,00,00,00,00,00,00,00},
        {00,88, 2,77,73, 7,63,67,00,00,00,00,00,00,00,00},
        {00,99,65, 4,28, 6,16,70,92,00,00,00,00,00,00,00},
        {00,41,41,26,56,83,40,80,70,33,00,00,00,00,00,00},
        {00,41,48,72,33,47,32,37,16,94,29,00,00,00,00,00},
        {00,53,71,44,65,25,43,91,52,97,51,14,00,00,00,00},
        {00,70,11,33,28,77,73,17,78,39,68,17,57,00,00,00},
        {00,91,71,52,38,17,14,91,43,58,50,27,29,48,00,00},
        {00,63,66, 4,68,89,53,67,30,73,16,69,87,40,31,00},
        {00, 4,62,98,27,23, 9,70,98,73,93,38,53,60, 4,23}
};
void count(int x,int y,int sum)
{
        if(y==16)
        {
                max1=max(max1,sum);
        }
        else
        {
                sum+=map[y][x];
                count(x,y+1,sum);
                count(x+1,y+1,sum);
        }
}

int main()
{
        count(1,1,0);
        cout<<"最大的和是："<<max1;
}

DetConan

python3 用时0.000216秒
结果是1074, 75, 64, 82, 87, 82, 75, 73, 28, 83, 32, 91, 78, 58, 73, 93

import time

start = time.clock()
nums = [[75],
        [95, 64],
        [17, 47, 82],
        [18, 35, 87, 10],
        [20, 4, 82, 47, 65],
        [19, 1, 23, 75, 3, 34],
        [88, 2, 77, 73, 7, 63, 67],
        [99, 65, 4, 28, 6, 16, 70, 92],
        [41, 41, 26, 56, 83, 40, 80, 70, 33],
        [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
        [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
        [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
        [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
        [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
        [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]]

lens = len(nums)
biglist = []
for i in range(lens):
    biglist += [[nums[lens - 1][i], nums[lens - 1][i]]]

for i in range(lens - 1):
    temp = biglist
    n = lens - 2 - i
    biglist = []
    for j in range(n + 1):
        tempn = nums[n][j]
        if temp[j][0] > temp[j + 1][0]:
            biglist += [[tempn + temp[j][0]] + [tempn] + temp[j][1:]]
        else:
            biglist += [[tempn + temp[j + 1][0]] + [tempn] + temp[j + 1][1:]]
print(biglist[0])

end = time.clock()
print("read:%f s" % (end - start))

cwhsmile

import time
import math

def test1():
    nums = [[75],
        [95, 64],
        [17, 47, 82],
        [18, 35, 87, 10],
        [20, 4, 82, 47, 65],
        [19, 1, 23, 75, 3, 34],
        [88, 2, 77, 73, 7, 63, 67],
        [99, 65, 4, 28, 6, 16, 70, 92],
        [41, 41, 26, 56, 83, 40, 80, 70, 33],
        [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
        [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
        [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
        [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
        [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
        [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]]
    last_len = len(nums[-1])
    nums = nums[::-1]
    li = nums[0]
    
    for i in range(1,last_len):
        new = li[:]
        li = []
        for j in range(len(nums[i])):
            front = nums[i][j] + new[j]
            #print(front,end=',')
            rear = nums[i][j] + new[j+1]
            #print(rear)
            if front > rear:
                li.append(front)
            else:
                li.append(rear)
        #print(li)
    new = li[:]

    
    return max(new)



start = time.perf_counter()
print(test1())
end = time.perf_counter()
print(end-start)

成为极客

import time as t
start = t.perf_counter()
a=[[75],
   [95,64],
   [17,47,82],
   [18,35,87,10],
   [20,4,82,47,65],
   [19,1,23,75,3,34],
   [88,2,77,73,7,63,67],
   [99,65,4,28,6,16,70,92],
   [41,41,26,56,83,40,80,70,33],
   [41,48,72,33,47,32,37,16,94,29],
   [53,71,44,65,25,43,91,52,97,51,14],
   [70,11,33,28,77,73,17,78,39,68,17,57],
   [91,71,52,38,17,14,91,43,58,50,27,29,48],
   [63,66,4,68,89,53,67,30,73,16,69,87,40,31],
   [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]
for i in range(14,-1,-1):
   for j in range(i):
      if a[i][j]>a[i][j+1]:
         a[i-1][j] += a[i][j]
      else:
         a[i - 1][j] += a[i][j+1]
print(a[0][0])
end = t.perf_counter()
print(end-start)

1074
8.210900000000035e-05

永恒的蓝色梦想

C++ 0ms

#include<iostream>
using namespace std;
#define max(a,b) (a>b?a:b)


int main() {
    char i = 14, j;
    int arr[15][15] = {
        {75},
        {95, 64},
        {17, 47, 82},
        {18, 35, 87, 10},
        {20, 04, 82, 47, 65},
        {19, 01, 23, 75, 03, 34},
        {88, 02, 77, 73, 07, 63, 67},
        {99, 65, 04, 28, 06, 16, 70, 92},
        {41, 41, 26, 56, 83, 40, 80, 70, 33},
        {41, 48, 72, 33, 47, 32, 37, 16, 94, 29},
        {53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14},
        {70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57},
        {91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48},
        {63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31},
        {04, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 04, 23} 
    };

    while (j = i--) {
        while (j--) {
            arr[i][j] += max(arr[i + 1][j], arr[i + 1][j + 1]);
        }
    }

    cout << arr[0][0] << endl;
    return 0;
}

数据小随从

我不知道错在哪里，为什么大家的答案都是1074，我算的是1064

#include<stdio.h>
#include<stdlib.h>

#define N 15

void main()
{
        int a[N][N] = { {75},
                                        {95,64},
                                        {17,47,82},
                                        {18,35,87,10},
                                        {20,4,82,47,65},
                                        {19,1,23,75,3,34},
                                        {88,2,77,73,7,63,67},
                                        {99,65,4,28,6,16,70,92},
                                        {41,41,26,56,83,40,80,70,33},
                                        {41,48,72,33,47,32,37,16,94,29},
                                        {53,71,44,65,25,43,91,52,97,51,14},
                                        {70,11,33,28,77,73,17,78,39,68,17,57},
                                        {91,71,52,38,17,14,91,43,58,50,27,29,48},
                                        {63,66,4,68,89,53,67,30,73,16,69,87,40,31},
                                        {4,62,98,27,23,9,70,98,73,93,38,53,60,4,23} };

        for (int i = 0; i < N; i++)//打印三角形
        {
                printf("%*d", 45 - 3 * i, a[i][0]);
                for (int j = 1; j <= i; j++)
                {
                        printf("%6d", a[i][j]);
                }
                printf("\n");
        }

        int k = 1;
        int nums[15] = { 0 };
        int t = 0;
        nums[0] = a[0][0];
        int res = 0;
        while (k < N)
        {
                if (a[k][t] > a[k][t + 1])
                {
                        nums[k] = a[k][t];
                }
                else
                {
                        nums[k] = a[k][t + 1];
                        t = t + 1;
                }
                k++;
        }
        printf("产生的序列是\n");
        for (int i = 0; i < N; i++)
        {
                printf("%4d", nums[i]);
        }
        printf("\n");
        for (int i = 0; i < N; i++)
        {
                res += nums[i];
        }
        printf("三角形顶端走到底端的最大和为 %d\n", res);

        system("pause");
}

输出结果：
75
                                        95    64
                                     17    47    82
                                  18    35    87    10
                               20     4    82    47    65
                            19     1    23    75     3    34
                         88     2    77    73     7    63    67
                      99    65     4    28     6    16    70    92
                   41    41    26    56    83    40    80    70    33
                41    48    72    33    47    32    37    16    94    29
             53    71    44    65    25    43    91    52    97    51    14
          70    11    33    28    77    73    17    78    39    68    17    57
       91    71    52    38    17    14    91    43    58    50    27    29    48
    63    66     4    68    89    53    67    30    73    16    69    87    40    31
  4    62    98    27    23     9    70    98    73    93    38    53    60     4    23
产生的序列是
  75  95  47  87  82  75  73  28  83  47  43  73  91  67  98
三角形顶端走到底端的最大和为 1064

永恒的蓝色梦想

数据小随从 发表于 2020-6-30 17:23
我不知道错在哪里，为什么大家的答案都是1074，我算的是1064
#include
#include

用 <> 发代码！

数据小随从

永恒的蓝色梦想 发表于 2020-6-30 17:59
用  发代码！

谢谢，我以前一直不知道他们这个怎么发的，我以为要特殊的软件编辑

mathtimes

#include <iostream>
using namespace std;
#define max(x,y) ((x)>(y)?(x):(y))
int Array[]={
75,
95,64,
17,47,82,
18,35,87,10,
20,04,82,47,65,
19,01,23,75,03,34,
88,02,77,73,07,63,67,
99,65,04,28,06,16,70,92,
41,41,26,56,83,40,80,70,33,
41,48,72,33,47,32,37,16,94,29,
53,71,44,65,25,43,91,52,97,51,14,
70,11,33,28,77,73,17,78,39,68,17,57,
91,71,52,38,17,14,91,43,58,50,27,29,48,
63,66,04,68,89,53,67,30,73,16,69,87,40,31,
04,62,98,27,23, 9,70,98,73,93,38,53,60,04,23
};
#define width 15
void setmax(int i,int j)
{
    if(j == 0)
        Array[i*(i+1)/2+j] += Array[i*(i-1)/2+j];
    else if(j == i)
        Array[i*(i+1)/2+j] += Array[i*(i-1)/2+j-1];
    else
    Array[i*(i+1)/2+j] += max(Array[i*(i-1)/2+j],Array[i*(i-1)/2+j-1]);
}
int main()
{
    for(int i=1;i<width;i++)
        for(int j=0;j<=i;j++)
            setmax(i,j);
    int maxum = 0;
    for(int i=width*(width-1)/2+0;i<width*(width-1)/2+15;i++)
        if(maxum<Array[i])
            maxum = Array[i];
    cout << maxum;
}