[Dynamic Programming] Working Days & Path Counting & Matrix Chain Multiplication

Fibonacci Number

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

 

• Recursion
• Memoization
• Dynamic Programming

By Recursion

int F(int n) {
	if(n < 2) return 1;
    return F(n-1) + F(n-2);
}

 

F(10)에서 타고 들어가게 되면, 같은 것이 호출되는 경우가 굉장히 많아진다. 

노드들이 굉장히 많아지게 되고 엄청나게 느려진다. 

 

By Memoization

int FF[1000]

int init(){
	for (i = 2; i < 1000; i++) FF[i] = -1;
    FF[0] = FF[1] = 1;}

int F(int n){
	if(FF[n]!= -1) return FF[n];
    FF[n] = F(n-2) + F(n-1);
    return FF[n];
}

기록을 해둔 얘들은 바로 리턴이 되기 때문에, 간단한 재귀보다 더 빠르게 계산됨

따라서 O(n)에 계산이 가능하다

 

모든 재귀가 memoization이 되는 것은 아니다. 

결과 값만 의미가 있지, 내부 구조가 의미가 있는 경우에는 불가능하다.

 

By Dynamic Programming

memoization에서 계산되는 값들이 순서가 명확할 때 바꿀 수 있다. 

우리는 무조건, 뒤에 있는 인덱스의 값을 구하기 위해서는 앞에 있는 숫자가 계산이 되어야 한다는 것을 알고 있다. 

따라서 앞이 계산되어 있다고 확신하는 코드이기 때문에 DP로 짤 수 있는 것이다. 

int FF[1000];

int F(int n)
{
	FF[0] = FF[1] = 1;
    for(i = 2; i <= n; i++) FF[i] = FF[i-1] + FF[i-2];
    return FF[n];
}

 

---

Select Working Days

• Given Pay for each of N days
• Select Days to Work to Maximize Total Pay
• One Rule : You cannot work on Consecutive Days

5

3

7

2

6

8

4

9

라고 정해져 있다고 하자

 

앞에서부터 생각해보자! (나의 개인적인 견해.. 로는 아마 무조건 전에 계산하는 것이 계산되어있다는 전제 하에 실행시키는 방법이기 때문에 "순서대로" 생각해야하는 것이 아닐까 ..)

 

5일만 생각해보자 : 5, 7, 6이다 -> 이러면 다음날 일을 못하게 만들기 때문에 8에 일을 못한다. 이는 전체적으로 손해일 수 있음

그러면 두 가지 방법을 생각해보자.

1. 5일동안 일을 하면서 마지막날 일을 하는 경우

2. 5일동안 일을 하면서 마지막날 일을 하지 않는 경우

 

우리는 그 앞에 정확히 언제 일을 했는지는 생각할 필요가 없고, 마지막 날 일을 하는 것만 확인하면 된다. 

즉, 일을 한 날과 안한 날을 기준으로 생각하면 된다. 

몇 가지 정답을 계산하게 되면 그걸 쓸 수 있는 경우에 사용할 수 있다. 

일 O	5	3	12	7	18	20	22	29
일 X	0	5	5	12	12	18	20	22

 

즉, 일을 안한 날은, 앞에 있는 날 중에 큰 숫자를 고르면 최대이고

일을 한 날은 앞에 일을 안한 날에서 현재 일을 한 날의 숫자를 더해주면 된다.

 

따라서 각 배열의 칸의 정답을 결정짓는 "해"는 일을 하느냐 안하느냐의 차이이다.

 

int W(int a[], int n){
    int D[n+1][2]; D[1][0] = 0; D[1][1] = a[1];
    for(i = 2; i<=n; i++) {
    	D[i][0] = max(D[i-1][0], D[i-1][1]);
        D[i][1] = D[i-1][0] + a[i];
    }
    return max(D[n][0], D[n][1]);
}

 

---

Path Counting

각 지점까지 오는 것을 계산해서, 다음 지점을 구하기 위해서는, 전에 오는 경우의 수를 더해주기만 하면 된다. 

따라서 각 배열(점)의 정답을 결정짓는 "해"는 왼쪽에서 오는 경로 + 위에서 오는 경로이다.

 

---

Matrix Multiplication

• Multiply a Sequence of N Matrices : \(M_1\) * \(M_2\) ... * \(M_N\)
• Size of Mi is \(d_{i-1}\) by \(d_i\)

순서에 따라서 비용이 달라지는데, 어떤 순서가 비용이 더 적게 드는지 구하고자 한다. 

• Cij = Mi * Mi+1 * ... Mj를 계산한 최소 비용이라고 가정하자
• 전체 답은 C1n이다. 
• 마지막 곱하기가 무엇인지!! -> 즉 마지막 하나가 결정한다는 것

따라서 중간 정답을 결정짓는 "해"는 마지막 곱하기가 어떤 행렬인지이다.

 

C11, C22, C33 ... CNN -> 0

C12, C23, C34 .... CN-1N -> \(d_{i-1} \times d_i \times d_{i+1}\) 이 해당 행렬의 비용이다.

C13, C24 ... CN-2N -> (M1 * M2) * M3 인지, M1 * (M2 * M3)인지에 따라 다르다

 

어떤 것을 계산하기 위해서는 "나 보다 차이가 작은 것" 을 이용하므로 "이전" 값을 사용한다

 

int M(int d[], int n){
    int D[n+1][n+1];
    for(i = 1; i <= n; i++) D[i][i] = 0;
    for(s = 1; s <= n-1; s++)
        for(i = 1; i <= n-s; i++){
            minval = INF;
            for(k = i; k <= i + s -1; k++) minval = min(minval, D[i][j] + D[k+1][i+s] + D[i-1]*D[k]*D[i+s];
            D[i][i+s] = minval;
        }
    return D[1][n];
}