다이나믹 프로그래밍 적용 문제 (1) 행렬 경로 문제 설명 양수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 우하단까지 이동한다. • 이동 방법 (제약조건) - 오른쪽이나 아래쪽으로만 이동할 수 있다 - 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다 • 목표: 좌상단에서 우하단까지 이동하되, 방문한 칸에 있는 점수들의 최대합을 구한다. 점화식 maxSum[i, j] = 위치 (i, j) 에 이르는 최대합 m[i, j] = 위치 (i, j) 에 해당하는 원본 값 0 ( if i = 0 or j=0 ) m[i, j] + max(maxSum[i - 1, j], maxSum[i, j - 1]) ( else ) 최대합 = maxSum(n, n) (i, j)의 위치에 있는 값은 위치의 위쪽 혹은 왼쪽 ..
[알고리즘] 다이나믹 프로그래밍 적용 문제 (1) 행렬 경로
다이나믹 프로그래밍 적용 문제 (1) 행렬 경로 문제 설명 양수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 우하단까지 이동한다. • 이동 방법 (제약조건) - 오른쪽이나 아래쪽으로만 이동할 수 있다 - 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다 • 목표: 좌상단에서 우하단까지 이동하되, 방문한 칸에 있는 점수들의 최대합을 구한다. 점화식 maxSum[i, j] = 위치 (i, j) 에 이르는 최대합 m[i, j] = 위치 (i, j) 에 해당하는 원본 값 0 ( if i = 0 or j=0 ) m[i, j] + max(maxSum[i - 1, j], maxSum[i, j - 1]) ( else ) 최대합 = maxSum(n, n) (i, j)의 위치에 있는 값은 위치의 위쪽 혹은 왼쪽 ..
2021.09.03