BOJ_1932 정수 삼각형 Silver.1

문제 링크: https://www.acmicpc.net/problem/1932

점화식을 찾는건 어렵지 않은데

문제 조건이 1 <= N <= 500 이기 때문에
N = 1일때, 답을 출력하는 것을 주의해야 한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    private static int[][] arr;
    private static int[][] dp;
    private static int answer;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        arr = new int[N + 1][];
        dp = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        answer = dp[1][0] = arr[1][0];

        for (int i = 2; i <= N; i++) {
            for (int j = 0; j < i; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + arr[i][j];
                } else if (j == i - 1) {
                    dp[i][j] = dp[i - 1][j - 1] + arr[i][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
                }
                answer = Math.max(answer, dp[i][j]);
            }
        }
        System.out.println(answer);
    }
}