Project Euler问题67不太正确

Question

我有一段Python代码，是为第18个问题写的。

这段代码在解决问题18时运行得很好，但在解决问题67时就有点问题。我怎么也想不明白为什么。

triangle = [
[59],
[73, 41],
[52, 40, 9],
[26, 53, 6, 34],
[10, 51, 87, 86, 81],
[61, 95, 66, 57, 25, 68],
...
]

def max_adjacent(row,col):
    return max(triangle[row][col]+triangle[(row+1)][col], triangle[row][col]+triangle[(row+1)][(col+1)])

if __name__ == '__main__':
    row = len(triangle)-2
    while row >= 0:
        triangle[row] = [max_adjacent(row,triangle[row].index(i)) for i in triangle[row]]
        row -= 1
    print(triangle[0][0])

这个算法的思路是从倒数第二行开始，把这一行的每个数字替换成它自己加上下面一行中最大的相邻数字。（比如，在上面部分定义的三角形中，倒数第二行的10会被替换成105。）这个过程会一直循环，直到到达三角形的顶端（第0行），然后打印出这一行的第一个元素，这个元素现在就是最大和。

这样算出来的结果是7220，我知道这个结果接近但不正确。我想知道为什么它在问题18中能正确工作呢？

有没有人能看出我假设的或者做错了什么？

Answer 1

这段代码可能会对你有帮助。它是用Java写的，使用了动态规划的概念。

 public static int max(int a,int b)
{
    return a>=b?a:b;
}
public static int maxSumPath(int a[][],int cacher[][],int r,int k) 
{
    if(r==100)
        return 0;
    else if(cacher[r][k]!=0)
    {
        return cacher[r][k];
    }
    else
    {
        cacher[r][k] = cacher[r][k] + max(maxSumPath(a,cacher,r+1,k),maxSumPath(a,cacher,r+1,k+1)) + a[r][k];
        return cacher[r][k];
    }
}

Answer 2

问题可能出在你使用了 index 函数。如果你在一行中有一个数字出现了两次，index 函数总是会返回这个数字第一次出现的位置。

我想第18个问题的一行里没有重复的数字，而现在这个问题里有。