최적 하부 구조에서 실제 알고리즘으로 이동

Question

동적 프로그래밍에 대해 이해함에 따라 주어진 상황에서 최적 하부 구조 개념을 쉽고 쉽게 개발할 수 있습니다. 예를 들어, 행렬 체인을 곱하기 위해 최적의 순서를 찾으면 Ai * Ai + 1 * ... * Aj를 계산하는 데 필요한 최소 곱셈 횟수를 찾을 수 있음을 알게되었습니다 (자세한 내용은 유감입니다. Ai * ... Ak 및 Ak + 1 ... * Aj에 필요한 곱셈의 합을 최소화하는 i와 j 사이의 split/parenetheses 배치 지점 k를 찾아 실제 크기와 함께 제공되는 비용을 더합니다. 즉, M (i, j) = mink (M (i, k) + M (k + 1, j) + di-1dkdj).

마찬가지로 문자열의 가장 긴 회문 부속 문자열을 찾는 경우 인덱스 i와 j와 입력 배열 사이의 최대 길이 회선 길이의 길이 l [i, j]는 2 + l [i i, j의 요소가 동일하고 추가 될 수있는 경우, 또는 l [i + 1, j], l [i, j-1]의 최대 값 나는 무엇이든 섞는다 ...)

그러나 어떤 상황에서 어떻게 위의 내용이나 심지어 내용과 같은 이상적인 순서의 길이를 찾기 위해 이것을 알고리즘으로 변환합니까? 기본적으로 루프를 실행하여 모든 것을 표로 만든 다음 기본적으로 테이블에서 필요한 것을 선택합니다. 행렬 체인을 사용하면 정확하게 수행 할 수있는 것처럼 보이지만, 회문에서는 루프를 만드는 방법에 대해 약간 혼란 스럽습니다.

감사합니다.

Answer 1

기본적으로 루프를 실행하여 모든 것을 도표로 표시하고 본질적으로 테이블에서 필요한 것을 선택합니까?

간단히 말해서, 그렇습니다. 동적 프로그래밍은 원본 문제를 더 작게 만드는 (질문에 잘 설명되어 있음) 기본 사례를 만듭니다. 즉 솔루션이 분명하고 더 이상 문제를 하위 문제로 나누지 않아도되는 거의 항상 작은 상황입니다. 예를 들어 행렬 곱셈 예제에서 하위 문제가 2 행렬로 축소되면 더 이상 선택할 수 없게됩니다. 즉, 에을 그대로 사용하면됩니다. 회문의 예에서, 나는 길이가 1 인 부분 문자열의 기본 경우를 선택하는데, 이것은 분명히 회문입니다.

따라서 memoization 배열/행렬 등을 만든 후에는 일반적으로 그 배열에 기본 대소 문자를 설정하고 알고리즘을 실행합니다. 최종 조건은 대개 배열의 정확한 위치에 도달하거나 계산할 값이 없을 때 (배열/행렬 등에서 원하는 것을 선택하는 시점)

유용 할 정도로.