블 루 브리지 컵알고리즘 트 레이 닝디지털 삼각형

2606 단어 알고리즘
문제 설명 (그림 3.1 - 1) 은 디지털 삼각형 을 보 여 주 었 다.프로그램 을 만들어 서 이 경로 가 지나 간 숫자의 총 계 를 최대 로 계산 하 십시오.● 한 걸음 한 걸음 왼쪽 사선 을 따라 아래로 또는 오른쪽 사선 을 따라 아래로 내 려 갈 수 있다.● 1 < 삼각형 행 수 ≤ 100;● 삼각형 의 숫자 는 정수 0, 1, 99 이다.입력 형식 파일 에서 먼저 읽 은 것 은 삼각형 의 줄 수 입 니 다.
다음은 전체 삼각형 출력 형식 최대 총화 (정수) 사례 입력 5, 7, 3, 8, 1, 0, 2, 7, 4, 4, 5, 6 5 사례 출력 30 을 설명 합 니 다.
import java.util.Scanner;

/** * @author   * */
public class Main {

    /** * @param args */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[][] arr=new int[n][n];
        int[][] mat=new int[n][n]; 
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                arr[i][j]=sc.nextInt();
            }
        }
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<=i;j++){
                if(i==n-1){
                    mat[i][j]=arr[i][j];
                }else{
                    mat[i][j]=Math.max(arr[i][j]+mat[i+1][j],arr[i][j]+mat[i+1][j+1]);
                }
            }
        }
        System.out.println(mat[0][0]);
    }
}

좋은 웹페이지 즐겨찾기