기록공간

동적계획법을 사용하는 문제이다. 아래 층에 있는 수를 선택 할때에는 대각선 왼쪽과 오른쪽 중 하나만 선택이 가능하다는 조건을 상기하며 살펴보도록 하자. 층마다 저장해야 할 정수 값들이 늘어난다. 그렇기 때문에 값을 저장할때나 DP테이블로 사용할때 2차원 배열이 필요하다. 맨 위에 값은 하나이기 때문에 DP테이블에 맨 윗층은 한개의 값이 저장된다. 그리고 2층은 값이두개가 되며 맨 위층의 값과 더하여 DP 테이블에 2개의 값이 저장된다. 여기서 특성을 알수 있는데 양 사이드에 있는 값들은 무조건 왼쪽 값은 그 위층의 맨 왼쪽값과만 더할 수 있고, 오른쪽 값은 그 위층의 맨 오른쪽 값과만 더할 수 있다. 그리고 3층은 값이 세개가 되며 양 사이드 2개의 값은 위와 같은 규칙으로 더해지고, 중간 값 하나는 2..