\ # 1037: 숫자 삼각형

\ # 1037: 디지털 삼각형 은 동적 계획 으로 2 차원 배열 로 중간 정 보 를 저장 해 야 합 니 다.동적 기획 의 이 해 는 필자 의 또 다른 박문 hihicoder \ # 1038: 01 가방 을 참고 할 수 있다.위 에 아 는 대답 을 인용 하 였 다.제목 중의 세 가지 힌트: 힌트 1: 맹목적 인 욕심 은 바람 직 하지 않다. 검색 계산 이 너무 오래 걸 리 면 힌트 2: 기억 이 깊이 검색 하여 신의 위 세 를 과시 하고 너비 가 어 려 운 문 제 를 우선 푸 는 힌트 3: 귀납 적 으로 공식 을 제시 하고 번 거 로 움 을 줄 이 는 것 이 진리 이다.
이 문 제 는 욕심 산법 이 전체 국면 에서 가장 좋 은 것 에 이 르 지 못 하고 검색 은 주로 심도 있 는 검색 과 크로스 오 버 검색 으로 나 뉜 다.일반적인 검색 은 옮 겨 다 니 는 것 이다. 기억 깊 은 검색 은 중간 구 조 를 저장 한 다음 에 불필요 한 검색 을 피 하 는 것 이다.이것 은 이미 동 귀 와 약간 유사 한 것 이 있 는데, 바로 모두 이 문제 의 비효 율 적 인 특징 을 사용 한 것 이다.그러나 기억 깊 은 검색 은 서브 문 제 를 반복 적 으로 계산 하고 기억 너비 로 바 꾸 면 반복 적 으로 서브 문 제 를 계산 하 는 문 제 를 피 할 수 있 을 것 이다.동태 계획 의 한 특징 은 바로 상태 전이 공식 이다. 내 생각 에는 전달 공식 에 해당 하 는데 이것 은 흔히 문 제 를 해결 하 는 관건 이다.
다음은 참조 코드 입 니 다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sin = new Scanner(System.in);

        int numlines = Integer.valueOf(sin.nextInt());
        int n = numlines;
        sin.nextLine();

        int price[][] = new int[numlines][numlines];
        int getPrices[][] = new int[numlines][numlines];

        while (numlines-- != 0) {
            String tmp[] = sin.nextLine().split(" ");
            for (int i = 0; i < n - numlines; i++) {
                price[n-numlines-1][i] = Integer.valueOf(tmp[i]);
            }
        }

        getPrices[0][0] = price[0][0];
        for (int i = 1; i < price.length; i++) {
            for (int j = 0; j < price[0].length; j++) {
                if (j == 0) {
                    getPrices[i][j] = getPrices[i-1][j] + price[i][j];
                } else if (i == j) {
                    getPrices[i][j] = getPrices[i-1][j-1] + price[i][j];
                } else {
                    getPrices[i][j] = Math.max(getPrices[i-1][j-1], getPrices[i-1][j]) + price[i][j];
                }
            }
        }

        int res = getPrices[n-1][0];
        for (int i = 1; i < n; i++) {
            if (getPrices[n-1][i] > res) {
                res = getPrices[n-1][i];
            }
        }
        System.out.println(res);
    }

}