せいすうさんかくけい

質問する

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

入力

第1行は三角形の大きさn(1≦n≦500)を与え、第2行からn+1行は整数三角形を与える.

しゅつりょく

最初の行と最大パスの数の和を出力します.

解法

ダイナミックプランニング法を使用して解決される問題.
すべてのパスで最大値を検索できますが、三角形のサイズが大きいほど、所要時間が長くなり、幾何級数が増加します.
問題を解析する場合は、現在の位置で次の2つの数のうちの1つを選択して、大きいものを選択します.
人の話を借りる
これは、「値を選択する方法は、左上隅の値または右上隅の値から大きな値を選択して値を追加することです.」
著者occidere

ソース:エンコードとデバッグの間(著者:occidere)
説明が上手な写真を探して持ってきました.
増加した値の計算を続ける必要はありません.配列を作成して保存するだけです.
値を保存するときに新しい配列を作成したり、元の三角形の値を保存する配列を更新したりできます.
しかし,資源の利用を減らすためには,既存の三角形ストレージのアレイを用いたほうがよい.

コード(Python)

H = int(input())
T = []
for i in range(H):
    input_ = input()
    line = list(map(int, input_.split(' ')))
    assert len(line) == i + 1
    T.append(line)

k = 2
for i in range(1, H):
    for j in range(k):
        if j == 0:
            T[i][j] = T[i][j] + T[i - 1][j]
        elif i == j:
            T[i][j] = T[i][j] + T[i - 1][j - 1]
        else:
            T[i][j] = max(T[i - 1][j - 1], T[i - 1][j]) + T[i][j]
    k += 1
print(max(T[H - 1]))