196.整数三角形

1.動的プログラミング

n = int(input())
dp = []

for _ in range(n):
  dp.append(list(map(int, input().split())))

for i in range(1, n):
    for j in range(i + 1):
      #왼쪽 위에서 내려오는 경우
      if j == 0:
        up_left = 0
      else:
        up_left = dp[i - 1][j - 1]
      #위에서 내려오는 경우
      if j == i:
        up = 0
      else:
        up = dp[i - 1][j]
      #최대 합 저장
      dp[i][j] = dp[i][j] + max(up_left, up)

print(max(dp[n - 1]))

2. C++

#include <bits/stdc++.h>

using namespace std;

int n;
int dp[500][500]; // 다이나믹 프로그래밍을 위한 DP 테이블 초기화

int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i + 1; j++) {
            cin >> dp[i][j];
        }
    }
    // 다이나믹 프로그래밍으로 2번째 줄부터 내려가면서 확인
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            int upLeft, up;
            // 왼쪽 위에서 내려오는 경우
            if (j == 0) upLeft = 0;
            else upLeft = dp[i - 1][j - 1];
            // 바로 위에서 내려오는 경우
            if (j == i) up = 0;
            else up = dp[i - 1][j];
            // 최대 합을 저장
            dp[i][j] = dp[i][j] + max(upLeft, up);
        }
    }
    int result = 0;
    for (int i = 0; i < n; i++) {
        result = max(result, dp[n - 1][i]);
    }
    cout << result << '\n';
}