동적계획법(Dynamic programming)-2

행렬 경로 문제

- 정수들이 저장된 n x n 행렬의 좌상단에서 우하단까지 이동한다.

단 오른쪽이나 아래쪽 방향으로만 이동할 수 있다.

- 방문한 칸에 있는 정수들의 합이 최소화되도록 하라.

Recursive algo.

int mat(int i, int j)

{

if (i==1 && j==1)

return m[i][j];

else if(i==1)

return mat(1,j-1) + m[i][j];

else if(j==1)

return mat(i-1,1) + m[i][j];

else

return Math.min(mat(i-1,j) , mat(i,j-1) ) + m[i][j];

}

=> 비효율적

Memoization

:계산된 결과값을 캐시에 저장

int mat(int i, int j)

{

if(L[i][j] != -1)

return L[i][j];

if (i==1 && j==1)

L[i][j] = m[i][j];

else if(i==1)

L[i][j] = mat(1,j-1) + m[i][j];

else if(j==1)

L[i][j] = mat(i-1,1) + m[i][j];

else

L[i][j] = Math.min(mat(i-1,j) , mat(i,j-1) ) + m[i][j];

return L[i][j];

}

Bottom-up

: 특정한 방향이 있는게 아니라 순환식의 오른쪽 값이 먼저 계산되는 거

Common Trick

인덱스가 0부터 시작하기 떄문에 0인 자리에 무한대 값을 채워넣으면

코드가 단순해진다.

경로구하기