สมมติว่ามีอาร์เรย์ 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] เราเลือกหนึ่งองค์ประกอบจากทุกสับอาร์เรย์
พิจารณา sum(i) จะคืนค่าผลรวมน้อยที่สุดที่เป็นไปได้ ซึ่ง arr[i] เป็นส่วนหนึ่งของคำตอบและเป็นองค์ประกอบที่เลือกล่าสุด ผลลัพธ์ของเราคือ min ของ sum(i – 1), sum(i – 2), sum(i – 3) เนื่องจากเราเห็นว่ามีปัญหาย่อยทับซ้อน เราสามารถใช้แนวทาง Dynamic Programming เพื่อแก้ปัญหานี้
ตัวอย่าง
#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
