[テストエンコーディング]整数三角形

4584 ワード
コーディングテスト テキストリンク
問題の説明

上の三角形の上部から下部へのパスでは、最大のマージ数を検索します.セルを下に移動する場合は、1つのセルの右または左側のみが対角線方向に移動できます.たとえば、3では、次のセルの8または1にのみ移動できます.
三角形情報を含む配列三角形をパラメトリック化する場合は、解いた関数を完了して、経過した数値の最大値を返します.
せいげんじょうけん
三角形の高さは1または500以下です.
三角形を構成する数字は0または9999を超えない.
I/O例
triangle result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30
コードを書くのは簡単ですが、解決策を考えるのに時間がかかる問題です.
三角形の2行目から、その真上の1つ(数値行の先頭または末尾の場合)または2つの数のうちの1つの大きな数を1つの値に変換し、一番下の行に計算します.
私が書いたコード
def solution(triangle):
    answer = 0
    m = len(triangle)
    high = 0
    
    for i in range(1, m):
        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:
                high = max(triangle[i-1][j], triangle[i-1][j-1])
                triangle[i][j] += high
    
    # print(triangle[m-1])
    
    return max(triangle[m-1])
[ZeroBase]テーブル列データ(Time Series Data)
h 2データベースSpringbootでの設定方法