최적의 하부 구조는 하위 문제에 대한 최적의 솔루션의 조합으로 주어진 최적화 문제에 대한 솔루션을 얻을 수 있음을 의미합니다. 이러한 최적 하부 구조는 일반적으로 재귀에 의해 설명된다. 예를 들어 그래프 G=(V,E)가 주어지면 정점v에 이르는 최단 경로 p는 최적의 하부 구조를 나타낸다: 이 가장 짧은 패스 p에 있는 중간 정점 w를 취합니다. p가 진정으로 가장 짧은 경로인 경우 w에서 w로 w및 p2로 하위 경로 p1로 분할 할 수 있습니다. 따라서 벨만 포드 알고리즘 또는 플로이드-워샬 알고리즘이 수행하는 재귀 방식으로 최단 경로를 찾기 위한 솔루션을 쉽게 공식화할 수 있습니다. k {displaystyle k}를 k {displaystyle k} th 층에서 떨어뜨릴 때 계란이 끊어지도록 하는 총 바닥 수로 보자 (위의 예는 k = 37 {displaystyle k=37} 를 취하는 것과 같습니다). 특히, fib(2)는 처음부터 세 번 계산하였다. 더 큰 예에서는 fib 또는 하위 문제의 더 많은 값이 다시 계산되어 지수 시간 알고리즘으로 이어집니다. 예를 들어, 와인의 가격이 선반에 배치될 때(왼쪽에서 오른쪽으로 순서대로): p1=1, p2=4, p3=2, p4=3.

최적의 해결책은 총 이익 1 * 1 + 3 * 2 + 3 + 4 * 4 = 29의 주문 p1, p4, p3, p2로 와인을 판매하는 것입니다. 이 전략은 두 와인이 같은 비용을 때 무엇을 언급하지 않지만, 이 전략은 바로 느낀다. 그러나 불행히도 다음 예제에서 볼 수 있듯이 그렇지 않습니다. 예를 들어, 80, 40, 30.s[i]로 i와 같은 인덱스가 더 크거나 같은 단어에 대해 가장 좋은 정당화 결과를 처리해 보겠습니다. 이 방정식의 첫 번째 줄은 가장 낮은 바운드에서 1에 인덱싱된 제곱으로 모델링된 보드와 가장 높은 바운드의 n을 다룹니다. 두 번째 줄은 마지막 순위에서 일어나는 일을 지정합니다. 기본 케이스를 제공합니다. 세 번째 줄인 재귀는 중요한 부분입니다.

예제에서 A, B, C, D 용어를 나타냅니다. 이 정의에서 우리는 q (i, j)에 대한 간단한 재귀 코드를 파생 시킬 수 있습니다. 다음 의사 코드에서 n은 보드의 크기, c(i, j)는 비용 함수이고 min()은 값 수의 최소값을 반환합니다: 두 예제 모두에서 fib(2)를 한 번만 계산한 다음 fib(4)과 fib(3)를 모두 계산하는 데 사용합니다. , 대신 그들 중 하나가 평가 될 때마다 그것을 계산합니다. 예를 들어 행렬 A, B 및 C를 곱해 보겠습니다. 치수가 각각 m×n, n×p 및 p×s라고 가정해 보겠습니다. 행렬 A×B×C는 m×s 크기이며 아래 표시된 두 가지 방법으로 계산할 수 있습니다. 아래의 실제 경로에 대해 설명합니다. 이것은 Fibonacci 숫자 예제와 마찬가지로 겹치는 하위 문제 특성을 나타내기 때문에 끔찍하게 느립니다. 즉, 동일한 경로 비용을 반복해서 다시 계산합니다. 그러나 함수를 사용하는 대신 경로 비용을 2차원 배열 q[i, j]에 저장하면 상향식으로 훨씬 빠르게 계산할 수 있습니다.

이렇게 하면 다시 계산할 수 없습니다. 배열 q[i, j]에 필요한 모든 값은 한 번만 미리 계산됩니다. (i,j)에 대한 미리 계산된 값은 필요할 때마다 간단히 조회됩니다. 행렬 체인 곱셈은 동적 프로그래밍의 유용성을 보여 주는 잘 알려진 예입니다. 예를 들어 엔지니어링 응용 프로그램은 행렬 체인을 곱해야 하는 경우가 많습니다. 예를 들어 100 ×100과 같은 큰 치수의 행렬을 찾는 것은 놀라운 일이 아닙니다. 따라서, 우리의 임무는 행렬 A 1, A 2를 곱하는 것입니다 . . . . . n {디스플레이 스타일 A_{1}, A_{2},….

A_{n}} .