[SWEA DP] 실전문제1 - 숫자판 놀이

이 게시글은 SW Expert Academy의 「SW 문제해결 심화 - 동적계획법」 강좌를 바탕으로 작성되었습니다.문제N * M 크기의 숫자판에서 위에서 아래로 가면서 계속 더한다고 할 때, 그 경우 결과가 가장 큰 값은?이동은 , ↓, 중 하나이다.위처럼 숫자판이 있다고 할 때, 첫줄은 그대로 있고 2행 1열(-5)부터 계산하기 시작한다.

그 때 2행 1열로 이동할 수 있는 칸은 1행 1열(10)과 1행 2열(2) 두 Cell이 가능하다.10 + (-5) > 2 + (-5)이므로 1행 1열에서 내려온 값으로 2행 1열의 값을 10 + (-5) = 5로 갱신한다.2행 2열(7)의 경우는 1행 1열(10), 1행 2열(2), 1행 3열(8)이 접근할 수 있다. 이 때 최댓값이 1행 1열 10이므로..........