동적 프로그래밍의 패턴

고지 사항: 아래에 설명된 방법은 보편적이지 않지만 종종 문제를 해결하거나 올바른 솔루션을 찾는 데 도움이 될 수 있습니다.

문제가 배열을 교차하지 않는 하위 세그먼트(연속 요소 시퀀스)로 최적의 방식으로 분할(또는 적합한 분할 수 계산)해야 한다는 사실로 귀결되는 경우 해결을 시도할 가치가 있습니다. 동적 프로그래밍을 사용합니다.

솔루션 체계의 예는 다음과 같습니다.
dp[i] - 첫 번째 i 요소에 대한 응답

dp[i] 계산: 첫 번째 i번째 요소만 고려하고 있으므로 i번째 요소가 마지막 요소가 됩니다. 즉, 이 요소는 마지막 하위 세그먼트에 있고 동시에 가장 오른쪽에 있습니다. 따라서 마지막 하위 세그먼트 j의 왼쪽 경계를 반복할 수 있습니다. 열거하는 과정에서 이 subsegment의 값을 계산하고 맞다면 dp[i]부터 dp[j - 1]까지 그리고 subsegment [j;i]의 값을 다시 계산합니다.

다음과 같은 간단한 문제를 생각해 보십시오. 정수 배열이 주어졌을 때 각 숫자가 일부 하위 세그먼트에 포함되고 각 하위 세그먼트에 동일한 숫자가 포함되도록 최소 개수의 교차하지 않는 하위 세그먼트로 분할해야 합니다. 예를 들어 배열 1 2 2 3 3 3 2 1 1의 경우 최적 분할은 다음과 같습니다. [1] [2 2] [3 3 3] [2] [1 1]. 이 작업은 배열을 통과하는 것만으로 쉽게 해결되지만(동일한 연속 요소를 모두 하나의 하위 세그먼트에 넣음) 예를 들어 동적 프로그래밍을 사용하여 해결합니다.
  정수; cin>> N; // 배열을 1-인덱스로 채움 벡터 arr(n + 1); for (int i = 1; i <= n; i++) cin>> 도착[i]; // 초기에 +oo를 dp 값으로 설정 벡터 dp(n + 1, 1000000000); // 길이가 0인 배열은 분할할 필요가 없으므로 이에 대한 대답은 0입니다. dp[0] = 0; // 오름차순 i에서 dp[i]에 대한 답을 계산합니다. for (int i = 1; i <= n; i++) { // 현재 arr[i]는 마지막 요소이므로 마지막 하위 세그먼트에서 가장 오른쪽 숫자가 됩니다. // 이 마지막 하위 세그먼트가 시작된 위치에 대한 모든 옵션을 반복합니다. for (int j = i; j > 0; j--) { if (arr[j] != arr[i]) { // 마지막 요소와 같지 않은 요소를 만나면 하위 세그먼트에 다른 숫자가 포함되며 이는 조건에 맞지 않습니다. // 계속할 필요가 없습니다. 왜냐하면 왼쪽 테두리를 왼쪽으로 이동해도 이 요소는 사라지지 않으므로 중단합니다. 부서지다; } // 마지막 하위 세그먼트가 [j;i]라고 가정합니다. // 따라서 첫 번째 j-1 요소의 최적 분할을 취하고 1을 더해야 합니다(하위 세그먼트 [j; i] 자체) dp[i] = min(dp[i], dp[j - 1] + 1); } } cout << dp[n];
요소가 하위 세그먼트에 속하지 않을 수 있는 경우 dp[i] = dp[i - 1]과 같이 적절한 옵션을 고려해야 합니다.

배열을 정확히 k개의 하위 세그먼트로 분할해야 하는 경우 동적 프로그래밍에서 두 번째 매개변수(분할할 세그먼트 수)가 추가됩니다.
즉, 이제 다음 dp를 고려할 것입니다.
dp[i][j]는 첫 번째 i개 요소를 정확히 j개의 세그먼트로 나눈 경우에 대한 답입니다.
잘못된 상태에 주의하세요.

역학의 재계산은 동일하지만 두 번째 매개변수를 고려합니다. 즉, dp[i][k]를 세고 마지막 하위 세그먼트 j의 왼쪽 경계를 통해 정렬하면 dp[i][k]를 통해 dp[j - 1][k - 1]과 세그먼트의 값을 다시 계산합니다. [j;i].

고지 사항: 아래에 설명된 방법은 보편적이지 않지만 종종 문제를 해결하거나 올바른 솔루션을 찾는 데 도움이 될 수 있습니다.

일부 축(일반적으로 시간 축 또는 일부 배열의 인덱스)에 위치한 일련의 간격이 있고 선택한 간격이 교차하지 않도록 최적의 방법으로 일부를 선택해야 하는 경우 동적 프로그래밍을 사용해야 합니다. .

대략적인 솔루션 체계:

처음에는 사용 가능한 간격을 오른쪽 경계로 정렬합니다. 다음 역학을 시작하겠습니다. dp[i] - 첫 번째 i 간격에 대한 답입니다. 
다음과 같이 다시 계산합니다. 먼저 이 간격이 사용되지 않는 상황을 고려한 다음 dp[i] = dp[i-1]만 고려합니다. 이것은 i가 커짐에 따라 dp[i]의 값이 감소하지 않도록 보장합니다. 그리고 이것은 논리적이기 때문입니다. 새로운 격차를 추가한다고 해서 전체적인 답변을 악화시킬 수는 없습니다. 단순히 새로운 격차를 무시하거나 이를 사용하여 더 수익성 있는 변형을 구성합니다. 이제 i번째 간격을 사용하려면 겹치지 않는 간격 세트를 선택해야 하므로 오른쪽 경계가 현재 간격의 왼쪽 경계보다 작은 간격을 사용할 수 있습니다. 이를 위해 처음에는 오른쪽 경계를 기준으로 간격을 정렬하여 이제 필요한 위치를 효율적으로 찾을 수 있습니다. 가능하면 분석적으로 수행할 수 있지만 일반적으로 오른쪽 경계가 현재 경계의 왼쪽 경계보다 작고 동시에 가능한 최대값인 binsearch로 간격을 찾을 수 있습니다. 하나. 우리는 탐욕스러운 이유로 올바른 경계를 최대화하려고 합니다. 내가 성장함에 따라 대답은 증가할 수 밖에 없습니다. 따라서 필요한 위치 p를 찾고 dp[i]를 통해 dp[p]와 i번째 간격을 다시 계산합니다.