[動的プログラミング]整数三角形-PISN

質問する

上の三角形の上部から下部へのパスでは、最大のマージ数を検索します.セルを下に移動する場合は、1つのセルの右または左側のみが対角線方向に移動できます.たとえば、3では、次のセルの8または1にのみ移動できます.
三角形情報を含む配列三角形をパラメトリック化する場合は、解いた関数を完了して、経過した数値の最大値を返します.

せいげんじょうけん

三角形の高さは1または500以下です.

三角形を構成する数字は0または9999を超えない.

I/O例

triangleresult[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]30

に答える

def solution(triangle):
    #memoization을 위한 depth
    depth = []
    #triangle 길이 만큼 빈배열로 초기화
    for _ in range(len(triangle)):
        depth.append([])
    depth[0].append(triangle[0][0])
    for i in range(1,len(triangle)):
        for j in range(i+1):
            #맨 왼쪽은 전  depth[전단계][0]에서 현재 triangle더하기
            if j == 0:
                depth[i].append(depth[i-1][0]+triangle[i][j])
            #맨 오른쪽은 depth[전단계][j-1]에서 현재 triangle더하기
            elif j == i:
                depth[i].append(depth[i-1][j-1]+triangle[i][j])
            #중간인 경우 depth[전단계][j-1]과 depth[전단계][j] 중에 큰 수를 현재 triangle에 더하기
            else:
                depth[i].append(max(depth[i-1][j-1],depth[i-1][j])+triangle[i][j])
    #가장 아래층에서 가장 큰수 구해서 return
    return max(depth[len(depth)-1])
print(solution([[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]))

💡TIL

最初は、状況ごとに各位置に到達する数を見つけたいと思っていました.
例)深さ[2]の[10,[11,16],15]
一次解はmemorizationに格納され,解は動的プログラミングの定義ではない.すなわち,各位置に到達した全ての場合,その位置で解を求めるだけで数量を保存する必要はない.