白駿1932-整数三角形

5983 ワード
白駿 アルゴリズム#アルゴリズム# ダイナミックプログラミング テキストリンク

質問する


問題リンク(白準1932-整数三角形)

上図は大きさ5の整数三角形の様子です.
一番上の7階から、下の1つの数を選択し、今まで、選択した数の和の最大のパスを求めるプログラムを作成しました.階下の数は、現在のレイヤで選択した数の対角線の左側または対角線の右側からのみ選択できます.
三角形の大きさは1以上500以下です.三角形を構成する各数は整数であり、0以上9999以下の範囲である.

に答える

dpを利用して問題を解決した.

入力値の処理


n変数入力高さを受け入れ、三角形配列を宣言します.
複文の周囲に三角形の配列を入力します.

アルゴリズム#アルゴリズム#


現在位置データムで、左下、右下の大きい値を現在位置に追加します.
triangle[posX][posY] = max(triangle[posX + 1][posY],
			   triangle[posX + 1][posY + 1])
次に、三角形の最上位位置の値を返します.

コード#コード#

import sys

input = sys.stdin.readline

def solution(n, triangle):
    for i in range(n - 1, 0, -1):
        for j in range(i):
            triangle[i - 1][j] += max(triangle[i][j], triangle[i][j + 1])

    return triangle[0][0]

if __name__ == '__main__':
    n = int(input())

    triangle = []
    for i in range(n):
        temp = list(map(int, input().split()))
        triangle.append(temp)

    result = solution(n, triangle)

    print(result)
今日書いたmakefileをバックアップします
配備[Bundler]Webpack Netlify|Npx|Degit