집에서 학교까지 갈 수 있는 거리 계산
가로8 세로5 = 13C5
지나갈 수 있는 길 분리
8x5
4x7x3 (이해x)
5x8
하지만 이건 사람이 풀 수 있게 되어있다.
모든 위치에 대한 방법의 갯수를 구하기
칸마다 주어진 입력 값으로 계산하기 떄문에 역시 어렵지 않다.
추천 시스템 등..페이스북에서 함께 아는 친구도 Path Counting사용!
네모들은 매트릭스
일정 범위 내의 값을 계산한다. (동그라미는 계산 값)
이전 시간에 나온 식 다시 설명하겠음
M1 x M2 x M3 x ... x Mn 을 계산하는 최적 cost는? => 너무 많다.
마지막 곱하기를 기준으로 생각하자. (어느 것을 마지막으로 곱할 것인가? )
M1 x M2 x M3 x ... x Mn
결합 법칙이 성립하기 때문에 어떤 순서로 곱하든 결과는 같다.
전체 비용을 최소화하기 위해서는 이 곱하기와 이 곱하기를 최소화
=> 뭘 마지막에 곱해야 하냐고?
다 해본다. M1이 마지막일 떄, M2이 마지막일 떄, M3이 마지막일 떄
왼쪽꺼 만드는 비용 + 오른쪽꺼 만드는 비용 + 제일 마지막 곱하는 비용
i,j = 3,9라고 하면
D(i,j) D(k+1,j)는
33 49
34 59
35 69
36 79
37 89
38 99
(차이값 6인데 6보다 차이나는 것은 없음)
차이가 작은 것부터 계산하자. 차이가 1인 것부터 n-1인 것까지
D11 D22 D33...은 차이가 0
ex) 1,4는 1,1과 2,4 1,2와 3,4 1,3와 4,4중 제일 작은 것
실제 코드 만들기(아직 이해 못함)
i+s = j
min을 취해서 D에 min을 넣어주기
시간: n^3
계산하는 값이 n^2개고 하나당 시간이 최대 n
