せいすうさんかくけい

🔗 質問リンク

https://programmers.co.kr/learn/courses/30/lessons/43105

問題の説明

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

⚠▼制限

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

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

💡 プール(言語:Python)

DP問題で解決しました.以前は漠然と関連の考えを見ていたので、簡単に解けたのを覚えています.

def solution(triangle):
    
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            
            # 삼각형 왼쪽 변 부분
            if j == 0:
                triangle[i][j] += triangle[i-1][j]
            # 삼각형 오른쪽 변 부분
            elif j == len(triangle[i])-1:
                triangle[i][j] += triangle[i-1][j-1]
            # 삼각형 중간 부분
            # 윗줄 두 수 중 최대값 하나만 더해줌
            else:
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
                
    # 마지막 행 최대값 = 총 최대값 케이스
    return max(triangle[-1])