整数三角形(ピラミッドの最大パス)

https://www.acmicpc.net/problem/1932
これは金字塔形の整数三角形の最上位から下までの時間値が最大の経路を求める問題である.
動的プログラミングを使用して解決できます.

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);
	}
}