Baek Junアルゴリズム|1932-整数三角形

14433 ワード
python algorithm バックアップアルゴリズム テキストリンク

▼▼問題

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

入力例

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

サンプル出力

30

最初の解


📝 解題-2 D配列の使用


動的プログラミングの問題でアレイを生成し,点火式を解くことで問題を生成すべきであると考えられる.
入力された配列値を2次元配列として生成し、注釈dも2次元配列として生成する.
         7
      10   16
    18   17   16
-> 17은 10과 16을 비교하여 더 높은 값인 16과 원래 있던 1을 더한 값이다.
  20   25   21   20
-> 25는 18과 17을 비교하여 더 높은 값인 18과 원래 있던 7을 더한 값이다.
24   30   27   27   25
  • 三角形の上部から、比較的大きな数ずつ、すべての加算を注釈バージョンに保存し、
  • 三角形の最後の行に大きな値が出力されます.
    • 点火式は以下の通り.
    d[i][j] = max(d[i-1][j-1], d[i-1][j]) + tri[i][j]
    このとき、iは三角形の行、jは列を表す.

    👩🏻‍💻 ソースコード-2 D配列の使用

    import sys

n = int(sys.stdin.readline().rstrip())
tri = []
for i in range(n):
    tri.append(list(map(int, sys.stdin.readline().split())))

d = [ [0] * n for _ in range(n) ]

d[0][0] = tri[0][0]
d[1][0] = tri[1][0] + tri[0][0]
d[1][1] = tri[1][1] + tri[0][0]

for i in range(2, n):
    for j in range(0, i+1):
        if j==0 :
            d[i][j] = d[i - 1][j] + tri[i][j]
        else:
            d[i][j] = max(d[i-1][j-1], d[i-1][j]) + tri[i][j]

print(max(max(d)))

    第二の解釈


    📝 問題解決-1 D配列の使用


    注記2 D配列を使用して問題を解くと、2 D配列の最後の行だけが必要になるため、2 D配列を使用する必要はありません.
             7
      10   16
    18   17   16
  20   25   21   20
24   30   27   27   25
    最小値を求めるには、最後の行、すなわちすべての値の合計のみが必要です.したがって、コメントは最後の行のみが必要になります.
    点火式は、2 D配列を使用する場合と同じです.

    👩🏻‍💻 ソースコード-プライマリ配列の使用

    import sys

n = int(sys.stdin.readline().rstrip())
tri = []
for i in range(n):
    tri.append(list(map(int, sys.stdin.readline().split())))

d = [0] * n

d[0] = tri[1][0] + tri[0][0]
d[1] = tri[1][1] + tri[0][0]

for i in range(2, n):
    for j in range(i,-1,-1):
        if j==0 :
            d[j] = d[j] + tri[i][j]
        else:
            d[j] = max(d[j-1], d[j]) + tri[i][j]

print(max(d))
    関数を利用してさらに時間を短縮する予定です!
    Rsync+sersyncデータバックアップ
    HTML Form