白駿1932号整数三角形(JAVA,DP)

<解答方法>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int [][] arr = new int [n][n+1];

		for(int i = 0 ; i < n ; i ++) {
			int cnt = 0;
			for(int j = 1 ; j < n+1 ; j++) {
				arr[i][j] = sc.nextInt();
				cnt++;
				if(i+1 == cnt)
					break;
			}
		}

		
		
		//초기값 설정
		arr[1][1] += arr[0][1];
		arr[1][2] += arr[0][1];
		for(int i = 2 ; i < n ; i ++) {
			for(int j = 1; j < n+1; j++) {
				//점화식  : 내 위에 2개중에 큰거를 선택해서 나한테 더해감
				arr[i][j] += Math.max(arr[i-1][j-1], arr[i-1][j]);
			}
		}
		
		int max = 0;
		for(int i =0 ; i < n+1 ; i++) {
			if(max < arr[n-1][i]) {
				max = arr[n-1][i];
			}
		}
		/*
		for(int i = 0 ; i < n ; i++) {
			System.out.println();
			for(int j = 0 ; j < n+1;j++) {
				System.out.printf("%d ", arr[i][j]);
			}
		}
		*/
		
		System.out.printf("%d", max);
	}


}