Tìm tổng tối thiểu sao cho một trong ba phần tử liên tiếp được lấy trong C ++

Giả sử chúng ta có một mảng gồm n phần tử. Nhiệm vụ là tìm tổng nhỏ nhất của các phần tử từ mảng. Sao cho ít nhất một phần tử, một phần tử được chọn trong số ba phần tử liên tiếp trong mảng đó. Vì vậy, nếu mảng giống như [1, 2, 3, 6, 7, 1]. Đầu ra là 4. Vì vậy, nếu chúng ta chọn 3 và 1, thì (3 + 1 =4). Vì vậy, có một số mảng con của các phần tử liên tiếp như [1, 2, 3], [2, 3, 6], [3, 6, 7], [6, 7, 1], chúng tôi đã chọn một phần tử từ mỗi mảng con.

Hãy xem xét sum (i) sẽ trả về tổng tối thiểu có thể có, trong đó arr [i] là một phần của lời giải và là phần tử được chọn cuối cùng. Khi đó kết quả của chúng ta là min của sum (i - 1), sum (i - 2), sum (i - 3). Như chúng ta có thể thấy rằng điều này có vấn đề con chồng chéo, khi đó chúng ta có thể sử dụng phương pháp lập trình động để giải quyết vấn đề này.

Ví dụ

#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);
}

Đầu ra

Minimum sum is: 4