[BOJ 1932整数三角形]

せいすうさんかくけい


例図の最値は7+3+8+7+5=30です.
「階下の数は、現在のレイヤで選択されている数の対角線の左側または対角線の右側からのみ選択できます.」したがって、再帰関係は次のように作成できます.
下のと元の数+max(対角線左、対角線右).
また、一番左、右には対角線の数字が1つしかないので、加算すればいいです.
完成した三角形の和は次のとおりです.

三角形の一番下の列の最低価格は私たちが探している答えです.

// 데이터 입력 생략
// a[i][j]

// 시작점과 경계(왼쪽, 오른쪽 대각선) 작업
dp[1][1] = a[1][1];
for (int i = 2; i <= n; i++) {
	dp[i][1] = dp[i - 1][1] + a[i][1];
	dp[i][i] = dp[i - 1][i - 1] + a[i][i];
}

// 재귀식을 이용하여 dp계산
for (int i = 3; i <= n; i++) {
	for (int j = 2; j < i; j++) {
		dp[i][j] = a[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j]);
	}
}

// 최댓값 찾기
int ans = -1;
for (int i = 1; i <= n; i++) {
	ans = max(ans, dp[n][i]);   // #include <algorithm>
}
printf("%d", ans);

実はa[i][j]とdp[i][j]を区別せず、一つのdp[i][j]でも解決できる.上の行の結果値は変更されないためです.
次のPythonコードはそのように書かれています.

N = int(input())

# 2차원 배열로 입력받기
dp = [list(map(int, input().split())) for _ in range(N)]

# 재귀식을 이용하여 dp[][] 계산하기
for i in range(1, N):
    for j in range(i+1):
        if j == 0:
            dp[i][j] += dp[i-1][j]
        elif 0 < j < i:
            dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])
        else:
            dp[i][j] += dp[i-1][j-1]

# 정답출력하기. dp[-1]은 마지막 행(1차원 배열)이다.
print(max(dp[-1]))