สมมติว่าเรามีอาร์เรย์ขององค์ประกอบ n ภารกิจคือการหาผลรวมขั้นต่ำขององค์ประกอบจากอาร์เรย์ อย่างน้อยหนึ่งองค์ประกอบ หนึ่งองค์ประกอบจะถูกเลือกจากทุกๆ สามองค์ประกอบที่ต่อเนื่องกันในอาร์เรย์นั้น ดังนั้นหากอาร์เรย์เป็นแบบ [1, 2, 3, 6, 7, 1] ผลลัพธ์คือ 4 ดังนั้นหากเราเลือก 3 กับ 1 แล้ว (3 + 1 =4) ดังนั้นจึงมีอาร์เรย์ย่อยขององค์ประกอบที่ต่อเนื่องกัน เช่น [1, 2, 3], [2, 3, 6], [3, 6, 7], [6, 7, 1] เราได้เลือกหนึ่งองค์ประกอบจากทุก subarray
พิจารณา sum(i) จะคืนค่าผลรวมขั้นต่ำที่เป็นไปได้ โดยที่ arr[i] เป็นส่วนหนึ่งของโซลูชันและเป็นองค์ประกอบที่เลือกล่าสุด จากนั้นผลลัพธ์ของเราคือ min of 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
