동적 기획(상세 요약+예제)

동규로 돌아가는 일반적인 전환 방법:
귀속 함수에는 n개의 매개 변수가 있는데 하나의 n을 수조로 정의한다. 수조의 하표는 귀속 함수 매개 변수의 수치 범위이고 수조 요소의 값은 귀속 함수의 귀환 값이다. 그러면 경계 값부터 점차적으로 수조를 채울 수 있고 귀속 함수 수치의 역과정에 해당한다.
동적 계획 문제 풀이의 일반적인 사고방식:
1. 원문제를 자문제로 분해
원문제를 몇몇 자문제로 분해하면 자문제와 원문제의 형식이 같거나 유사하다. 단지 규모가 작아졌을 뿐이다. 자문제는 모두 해결되고 원문제는 바로 해결된다(디지털 삼각형 예)
자 문제의 해답은 일단 구하면 보존되기 때문에 미국 자 문제는 단지 한 번만 해답할 수 있다
2. 상태 확인
동적 기획으로 문제를 풀 때 우리는 종종 하위 문제와 관련된 각 변수의 값을 추출하여 하나의'상태'라고 부른다.하나의'상태'는 하나 이상의 하위 문제에 대응한다. 이른바 어떤'상태'아래의'값'은 바로 이'상태'에 대응하는 하위 문제의 해답이다.
모든'상태'의 집합은 문제의'상태 공간'을 구성한다.'상태 공간'부터 크기까지 동적 기획으로 문제를 해결하는 시간의 복잡도와 직결된다.숫자 삼각형의 예에는 모두 N*(N+1)/2개의 숫자가 있는데, 이 모든 문제의 상태 공간에는 모두 N*(N+1)/2개의 상태가 있다
전체 문제의 시간 복잡도는 상태 수에 각 상태를 계산하는 데 필요한 시간을 곱하는 것이다
숫자 삼각형에서'상태'는 한 번만 지나갈 수 있고 모든 상태에서 계산하는 데 걸리는 시간은 N과 무관한 상수이다
동적 기획으로 문제를 풀면 K개의 정수 변수가 하나의 상태를 구성할 수 있다(예를 들어 디지털 삼각형의 중행호와 열호라는 두 변수가'상태'를 구성한다).만약 이 K개의 정형 변수의 수치 범위가 각각 N1, N2라면...Nk, 그러면 우리는 K차원의 수조array[N1][N2]를 사용할 수 있다.[Nk]은(는) 각 상태의 값을 저장합니다.이'값'이 반드시 하나의 정수나 부동점수는 아니다. 아마도 하나의 구조가 있어야만 표시할 수 있을 것이다. 그러면 array는 하나의 구조 수조가 될 수 있다.하나의'상태'아래의'값'은 통상적으로 하나 이상의 하위 문제의 해답이 될 수 있다
3. 일부 초기 상태(경계 상태)의 값을 결정합니다.
숫자 삼각형의 경우 초기 상태는 언더레이 숫자이고 값은 언더레이 숫자입니다.
4. 상태 이동 방정식 확인
'상태'가 무엇인지, 그리고 이'상태'아래의'가치'를 정의한 후에 서로 다른 상태 사이를 어떻게 이동하는지, 즉 어떻게 하나 이상의'가치'에서 알려진'상태'에서 다른'상태'의'가치'('사람마다 나'의 점프형)를 구해야 한다.상태의 이동은 귀속 공식으로 표시할 수 있고, 차귀속 공식도'상태 이동 방정식'이라고 할 수 있다.
디지털 삼각형의 상태 전환 방정식:

    MaxSum[r][j]=  D[r][j]    r==N
	               Max(MaxSum[r+1][j],MaxSum[r+1][j+1])+D[r][j]       

동적 기획으로 해결할 수 있는 문제의 특징
1) 문제는 최우수자 구조적 성격을 지닌다
만약 문제의 최우해에 포함된 자문제의 해도 최우라면 우리는 이 문제가 최우자 구조적 성격을 가지고 있다고 말할 것이다
2) 후효성 없음
현재의 몇몇 상태 값이 일단 확정되면 그 후 과정의 변화는 이 몇몇 상태의 값과 관계가 있을 뿐, 이전에 어떤 수단을 취했거나 어떤 경로를 거쳐 현재의 이 몇 가지 상태로 변했는지와 관계가 없다.