パスカルトライアングルの最大経路

Question

私はプロジェクトオイラーの問題18を解決しようとしています。ここを参照、https://projecteuler.net/problem=18。

def maxpath(triangle): 
    p = 0 
    total = 0 
    for x in range(0,len(triangle)): 
     if p + 1 < len(triangle[x]) - 1: 
      if triangle[x][p+1] > triangle[x][p]: 
       p += 1 
     total += triangle[x][p] 
    return total 

2次元のリストを指定すると、三角形の上端から下端までの最大ルートが見つかります。誰かがこのコードの何が間違っているか説明してもらえますか？

Answer 1

すべてがこの行を除いてチェックアウト：

if p + 1 < len(triangle[x]) - 1: 

がここに実際には二つの問題があります。最初の1つはp + 1の代わりにpでなければならないということです。それについて考えると、pの現在の値は前の行から、最初の行の後の行について引き継がれます。したがって、p + 1は明確に定義されています。実際には、2行目以降の繰り返しを1から始めることができ、その条件を持つ必要はありません。

2番目の問題はマイナーですが、毎回その長さを計算する必要はありません。行の長さは常に0のインデックス+ 1に等しいので、代わりにxと比較してください。

これはあなたのコードを固定した後のように見えるものです：

def maxpath(triangle): 
    p = 0 
    total = 0 
    for x in range(len(triangle)): 
     if p < x and (triangle[x][p + 1] > triangle[x][p]): 
       p += 1 
     total += triangle[x][p] 
    return total 

そして、あなたはさらにそれを最適化したい場合は、今、

maxpath([[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]) # Euler website example 

が

23 

---

を生成します（を削除する3210をチェックすると、これを行うことができます：

def maxpath(triangle):  
    p = 0 
    total = triangle[0][0] 
    for x in range(1, len(triangle)): 
     if triangle[x][p + 1] > triangle[x][p]: 
      ... # the rest stays the same