ProE 18/67 最大路径和

被人说这是动态结构真的吓死人…现在发现并不是

思路参考了知乎的一篇专栏

具体实现就是从倒数第二行开始,每一行加上下一行相邻两个数的最大值,一直加到第一行,这个用py太简单了。

Toyomu在想的时候也有这个想法,不过方向是自顶向下导致早早放弃了。

先来导入部分

导入部分

triangle ='''

'''.split("\n")
triangle = triangle[1:-1]

for i in range(0,len(triangle)):
    triangle[i] = triangle[i].split(" ")
    triangle[i] = list(map(int, triangle[i]))

实现部分-伊始

Toyomu在一开始就抛弃了正确的做法转向了一种很诡异的做法,具体做法是将三角一层一层剥开,像是剥洋葱一样,但是有一个巨大的问题,就是最后的终点总是会导向中间的一层,而且没有考虑到所有路径

def installation(lis):
    if len(lis)%2 == 0:
        mid = len(lis)>>1
        tri = max(lis[-1][mid],lis[-1][mid-1])+lis[-2][mid-1]
        rowindex = mid-1
        colindex = -2
    else:
        tri = lis[-1][len(lis)//2]
        rowindex = len(lis)//2
        colindex = -1
    ans = [rowindex,colindex,tri]
    return ans

def barsum(list,row,col,n):
    ans = 0
    for i in range(-col):
        ans += list[i+col][row-((-1)**n)+i*n]
    return ans

def compare(list,row,col,tri):
    lfact = list[col-1][row-1]
    rfact = list[col-1][row]
    a1 = lfact+tri
    a2 = rfact+tri
    a3 = lfact+(barsum(triangle,row,col,0))
    a4 = lfact+(barsum(triangle,row,col,1))
    return max(a1,a2,a3,a4)

def maxpath(lis):
    index = installation(lis)
    rindex = index[0]
    cindex = index[1]
    ans = index[-1]
    while rindex > 0:
        ans = lis[cindex-2][rindex-1]+compare(lis,rindex,cindex,ans)
        cindex -= 2
        rindex -= 1
    return ans
print(maxpath(triangle))

实现部分-最后

看了知乎那个专栏之后就发现其实很简单,预计时间复杂度为O(n^2)

def maxpath(lis):
    index = -2
    while index >= 0 - len(lis):
        for i in range(0,len(lis[index])):
            lis[index][i] += max(lis[index+1][i],lis[index+1][i+1])
        index -= 1
    return lis[0][0]

真就当局者迷旁观者清咯.

未曾设想的道路-暴力法

Toyomu从来就没想过暴力,暴力对67题是无解的,不过我觉得Knight可以试一下18的暴力解法

点赞

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *