정수 삼각형(피라미드 최대 경로)

https://www.acmicpc.net/problem/1932
피라미드형 정수 삼각형에서 맨 위층부터 아래로 내려올 때 값이 최대가 되는 경로를 구하는 문제이다.
Dynamic Programming을 사용해서 해결할 수 있다.

import java.util.Scanner;
public class Main
{
    // 피라미드의 최소 경로 구하기. dp
    static int n; // n층 변수
    static int[][] A; // 값 저장되어있는 배열
    static int[][] dp; // 누적 값 저장 배열
    
	public static void main(String[] args) 
	{
	    Scanner sc = new Scanner(System.in);
	    n = sc.nextInt(); // 몇층인지 입력받음
	    
	    A = new int[n+1][n+1]; // 1번 인덱스부터 사용
	    dp = new int[n+1][n+1];
	    
	    // 값 저장되어있는 배열 입력받음
	    for (int i=1; i<=n; i++)
	    {
	        for (int j=1; j<=i; j++)
	        {
	            A[i][j] = sc.nextInt();
	        }
	    }
	    
	    dp[1][1] = A[1][1]; // 꼭대기는 미리 누적값에 저장
	    
	    for (int i=2; i<=n; i++)
	    {
	        for (int j=1; j<=i; j++)
	        {
	            if (j==1) // 1열일때
	                dp[i][j] = A[i][j] + dp[i-1][j];
	           else
	                dp[i][j] = A[i][j] + Math.max(dp[i-1][j], dp[i-1][j-1]);
	        }
	    }
	    
	    int max = 0;
	    for (int i=1; i<=n; i++)
	    {
	        if (dp[n][i] > max)
	            max = dp[n][i];
	    }
	    
	    System.out.println(max);
	}
}

dp배열을 따로 만들지 않고도 해결할 수 있다.

public class prac
{  
	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 몇층인지 입력받음
	    int[][] A = new int[n][n]; // 값 저장되어있는 배열
	    
	    // 값 저장되어있는 배열 입력받음
	    for (int i=0; i<n; i++) // 0부터 시작
	    {
	        for (int j=0; j<=i; j++)
	        {
	            A[i][j] = sc.nextInt();
	        }
	    }
	    
	    for (int i=1; i<n; i++)
	    {
	        for (int j=0; j<=i; j++)
	        {
	            if (j-1>=0) // j-1열이 0이상이면 == j>=1
	            // 즉 첫번째열 빼고 두번째 열 부터
	                A[i][j] = A[i][j] + Math.max(A[i-1][j], A[i-1][j-1]);
	            else // 첫번째 열
	                A[i][j] = A[i][j] + A[i-1][j];
	        }
	    }
	    
	    int max = 0;
	    for (int i=0; i<n; i++)
	    {
	    	if(max < A[n-1][i]) 
				max = A[n-1][i];
	    }
	    
	    System.out.println(max);
	}
}