[プログラマー]整数三角形Python


質問する


https://programmers.co.kr/learn/courses/30/lessons/43105

上の三角形の上部から下部へのパスでは、最大のマージ数を検索します.セルを下に移動する場合は、1つのセルの右または左側のみが対角線方向に移動できます.たとえば、3では、次のセルの8または1にのみ移動できます.
三角形情報を含む配列三角形をパラメトリック化する場合は、解いた関数を完了して、経過した数値の最大値を返します.

せいげんじょうけん

  • 三角形の高さは1または500以下です.
  • 三角形を構成する数字は0または9999を超えない.
  • I/O例



    アイデア


    三角形を順番に迂回し、その和を求め、三角形を更新します.
  • 周回って、一番左の方が右上から来る場合だけなので、元の数字に加算します.
  • で一番右の場合は左上からしか来ないので、元の数字に加算します.
  • の突き当たりではなく、真ん中で、両側から来ているので、左と右に大きな数を加えます.
  • 最後に最大の数を出力すればいいです.
  • ソリューション関数python

    def solution(triangle):
        for i in range(1, len(triangle)):
            for j in range(len(triangle[i])):
                if j == 0:  #left
                    triangle[i][j] += triangle[i-1][j]
                elif j == len(triangle[i])-1:   #right
                    triangle[i][j] += triangle[i-1][j-1]
                else:
                    triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
    
        return max(triangle[-1])