テストプログラマコード-整数三角形(Lv 3)

5952 ワード
アルゴリズム#アルゴリズム# データ構造 テキストリンク
問題を解く

DPテーブルの簡単な問題を作成できます。

  • 計算方法の経路を逆方向に追跡すると、直接上から来てもよいし、横から来てもよいし、2つの場合であってもよい.
  • の両端にあるのは例外処理です.
    • def solution(triangle):

    n = len(triangle[-1])
    dp = [[-1]*j for j in range(1,n+1)] # 테이블 생성
    dp[0]=triangle[0]
    # print(dp)
    
    for i in range(n):
        if i==0:
            continue;
        for j in range(i+1):
            if j==0:
                
                dp[i][j] = dp[i-1][j] + triangle[i][j]
            elif j==i:
                dp[i][j] = dp[i-1][j-1] + triangle[i][j]
            else:
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) +  triangle[i][j]    
    return max(dp[-1])
    ツリー番号
    C#——サイクルの中断