백준 1932번 - 정수 삼각형 (Java)

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

코드 :

dp - top down

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[][] seq;
    static Integer[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        seq = new int[n+1][n+1];
        dp = new Integer[n+1][n+1];

        //초기화
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= i; j++) {
                seq[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[1][1] = seq[1][1];
        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(recur(n, i), max);
        }
        System.out.print(max);
    }
    //dp[n1][n2] n1번째 행, n2번째 열의 수까지의 최댓값
    public static int recur(int row, int column){
        if(dp[row][column] == null){

            //왼쪽 맨끝인 경우
            if(column == 1){
                dp[row][column] = (recur(row - 1, 1)) + seq[row][column];

            //오른쪽 맨 끝인 경우
            } else if(column == row){
                dp[row][column] = (recur(row - 1, column - 1)) + seq[row][column] ;

            //끝이 아닌 경우들
            } else {
                dp[row][column] = Math.max(recur(row - 1, column), recur(row - 1, column - 1)) + seq[row][column];
            }
        }

        return dp[row][column];
    }
}