The Manhattan Tourist Problem, Chained Matrix Multiplication

위와 같은 문제가 있다고 하자.

위 식을 divde-and-conquer로 풀게 되면

            1 (i=0,j>0)

P(i,j)= 0 (i>0,j=0)

            (P(i-1,j)+P(i,j-1))/2 이 되고

T(n) = 2*T(n-1) + c가 되므로 O(2^n)이 되게 된다.

이를 해결하기 위해서는 중복된 값을 계산하지 않는 Dynamic Programming을 사용하면 된다.

---

Source에서 sink까지 갈 때, 어떻하면 최댓값으로 갈 수 있을까?

경우의 수는 총 2^n*2^m으로 exponential하다.

하지만 직전의 것과만 비교하면 경우의 수가 n*m개로 줄게 된다.

 

DP에서는 직전값들끼리 비교를하기 때문에 초깃값을 설정해주어야 한다. 2,3번은 초기값을 넣어준다는 말이다. 

1 번은 직전것들끼리 비교하여 최댓값을 고른다는 뜻이다.

시간복잡도는 O(n*m)이 된다.

---

Chained Matrix Multiplication

 

행렬의 곱셈에서 무엇을 먼저 계산하는지에 따라 연산횟수가 달라진다.

Table의 대각선에 초기값을 설정하고, A2*A7(i=2,j=7)을 구하고 싶다면 위처럼 색칠한 부분만 구하면 된다. 단, 한칸 움직일 때마다 반복문이 i에서 j-1번까지 돈다.

시간복잡도 계산