삼각 분할 (동적 계획법) 편집하기 (부분)

== 접근법 ==

* 전체 다각형을 작은 삼각형들로 쪼개면서, '''각 쪼갠 조각이 최적으로 분할되었다고 가정'''하고 전체 최적값을 계산한다.
* 이 문제는 구조적으로 Optimal Substructure (최적 부분 구조)와 Overlapping Subproblems (중복 부분 문제)를 가지므로 동적 계획법이 적합하다.
* 아래와 같은 표를 그린다. 각 행 열의 헤더는 각 꼭지점을 의미한다. 그리고 행열이 만나는 지점은 두 꼭지점이 잇는 선을 의미한다. 
** 같은 지점에서 같은 지점으로는 선이 그어지지 않으므로 무시한다.
** 연속된 두 점은 삼각형이 나올 수 없는 직선이므로 삼각 비용은 0이다.

{| class="wikitable"
|+
!
!1
!2
!3
!4
!5
|-
!1
!
|0
|
|
|
|-
!2
|
!
|0
|
|
|-
!3
|
|
!
|0
|
|-
!4
|
|
|
!
|0
|-
!5
|
|
|
|
!
|}


동적 계획법을 이용하여 최적 부분 문제를 정의하면 다음과 같다.
*'''dp[i][j]''' : 꼭짓점 vᵢ부터 vⱼ까지의 최소 삼각 분할 비용
*점화식:
  dp[i][j] = min(dp[i][k] + dp[k][j] + w(i, k, j))  
  (i < k < j)