Cho mảng n phần tử, tìm tổng nhỏ nhất của các phần tử được chọn sao cho trong mỗi 3 phần tử liên tiếp có ít nhất một được chọn. Ví dụ [1,2,3,6,7,1] → 4 (chọn 3 và 1).
Quy hoạch động: sum[i] = arr[i] + min(sum[i-3], sum[i-2], sum[i-1]). Kết quả min của 3 giá trị cuối.
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); }
Kết quả
Minimum sum is: 4