ダイナミックプログラミング技術
解決した問題の一部の答えをメモリに記録し、一度に計算した問題の再計算を回避する解決方法.
タワー
再帰関数を使用して小さな問題を呼び出し、大きな問題を解決します.
昇降方式
繰り返し文を使用して、まず小さな問題を解決し、解決した小さな問題を集中して大きな問題を解決します.
白駿1932号.

に質問

    7
   3 8
  8 1 0
 2 7 4 4    
4 5 2 6 5

上の図は、サイズ5の整数三角形を示しています.
一番上の7階から、一番上の7階から、下の1つの数字を選択します.今まで、選択した数字と最大パスを求めるプログラムを作成してください.選択できるのは、現在のレイヤで選択した数の対角線の左側または対角線の右側のみです.

入力例

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

出力例

30

💻 コード#コード#

n = int(input())

data = []

for i in range(n):
    data_list = list(map(int, input().split()))
    for j in range (n, i + 1, -1):
        data_list.append(0)
    data.append(data_list)

for i in range(n):
    for j in range(n):
        # 위에서 오는 경우
        if i == 0:
            up =  0
        else:
            up = data[i-1][j]
        # 왼쪽 위에서 오는 경우
        if i == 0:
            left_up = 0
        else:
            left_up = data[i-1][j-1]
        data[i][j] = data[i][j] + max(up, left_up)

print(max(data[n-1]))

デザイン

三角形をnxn配列に格納します.各層はリストに数字を格納し、n個から各層の数字を減算し、0に数字を埋め込む.

図のように交換してください.
では、現在のレイヤで選択した数値は、下または対角線の右側にある数値のみを選択できます.そこで、上と対角線の左から来る場合は、大きな数字を選んで最大にします.

📝 整理する

これは以前解決した金鉱問題とあまり差がない.