整数三角形-PYTHON

975 ワード
python アルゴリズム#アルゴリズム# テキストリンク

問題の説明



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

せいげんじょうけん


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

解答方法


まずこの問題を見て、直接やれば簡単です.両端の数は前の数を直接加算することができ、交差すると交差数の中で最大の数に置き換えられます.
  • 両端の数字であれば、問題に応じて更新すればよい、
  • 両端以外の数字の場合、前の数字より大きい場合、
    • の大きい数を更新します.
    def solution(triangle):
    answer = 0
    for i in range (1,len(triangle)):
        for j in range (i+1):
            if j == 0 :
                triangle[i][j] += triangle[i-1][j]
            elif j == i:
                triangle[i][j] += triangle[i-1][j-1]
            else :
                triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])
    answer = max (triangle[-1])    
            
    return answer
    GitHub+Hexo個人ブログを作成
    新浪のささやかなストラップ