개발 공부 - [동적계획법 (Dynamic Programming)] Dynamic Programming - 2

Basic Example

- 행렬 경로 문제

: 정수들이 저장된 n×n 행렬의 좌상단에서 우하단까지 이동한다. 단 오른쪽이나 아래쪽 방향으로만 이동할 수 있다.

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

Key Observation

세로 축 : i

가로 축 : j

=> (i,j)

(i,j)에 도달하기 위해서는 (i,j-1)

혹은 (i-1,j)를 거쳐야 한다.

또한 (i,j-1) 혹은 (i-1,j)까지는

최선의 방법으로 이동해야 한다.

순환식

L[i, j] : (1,1)  에서  (i,j)까지 이르는 최소합

L[i, j]  = 

mij                                               if i = 1 and j = 1;

L[i  1, j] + mij                                 if j = 1;

L[i, j  1] + mij                                 if i = 1;

min(L[i  1, j], L[i, j  1]) + mij               otherwise.

경로 구하기

void printPathRecursive(int i, int j)

    {

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

             print(1 + “ “ + 1);

         else {

             if (P[i][j] == ‘←’)

                 printPathRecursive(i, j-1);

             else

                 printPathRecursive(i-1, j);

             print(i + “ “ + j);

     }

}

이렇게 recursive 하게 구하는 게 낫다.

int mat() 같은 경우에도 for 문 두번 돌리면서 경로 구하는 형태임.