n개의 요소로 구성된 배열이 있다고 가정합니다. 작업은 배열에서 요소의 최소 합을 찾는 것입니다. 적어도 하나의 요소가 해당 배열의 모든 연속 3개 요소에서 하나의 요소가 선택되도록 합니다. 따라서 배열이 [1, 2, 3, 6, 7, 1]과 같은 경우. 출력은 4입니다. 따라서 3과 1을 선택하면 (3 + 1 =4)입니다. 따라서 [1, 2, 3], [2, 3, 6], [3, 6, 7], [6, 7, 1]과 같은 연속적인 요소의 하위 배열이 있습니다. 모든 하위 배열에서 하나의 요소를 선택했습니다.
sum(i)이 가능한 최소 합계를 반환한다고 생각하면 ar[i]는 솔루션의 일부이며 마지막으로 선택한 요소입니다. 그러면 우리의 결과는 sum(i – 1), sum(i – 2), sum(i – 3)의 최소값입니다. 중첩 하위 문제가 있음을 알 수 있으므로 동적 프로그래밍 접근 방식을 사용하여 이를 해결할 수 있습니다.
예시
#include <iostream>
using namespace std;
int minOfThree(int a, int b, int c) {
return min(min(a, b), c);
}
int getMinSum(int arr[], int n) {
int sum[n];
sum[0] = arr[0];
sum[1] = arr[1];
sum[2] = arr[2];
for (int i=3; i<n; i++)
sum[i] = arr[i] + minOfThree(sum[i-3], sum[i-2], sum[i-1]);
return minOfThree(sum[n-1], sum[n-2], sum[n-3]);
}
int main() {
int arr[] = {1, 2, 3, 20, 2, 10, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Minimum sum is: " << getMinSum(arr, n);
} 출력
Minimum sum is: 4