โปรแกรม C++ หาเส้นทางผลรวมต่ำสุดในสามเหลี่ยม

ข้อความโจทย์

กำหนดโครงสร้างสามเหลี่ยมของตัวเลข หาเส้นทางผลรวมต่ำสุดจากด้านบนลงล่าง แต่ละขั้นคุณอาจเคลื่อนที่ไปยังตัวเลขที่อยู่ติดกันบนแถวด้านล่าง

ตัวอย่าง

ถ้าอินพุตคือ:

    5
   7 3
  8 1 2
 9 6 4 5

ผลรวมต่ำสุดคือ 13 ดังนี้:

5 + 3 + 1 + 4

อัลกอริทึม

• ใช้เทคนิคการจดจำ (memorization) ของการเขียนโปรแกรมแบบไดนามิก (Dynamic Programming)
• สร้างอาร์เรย์ 1-D สำหรับการจดจำ คือ memorization
• สำหรับแต่ละแถว K ใช้สูตรด้านล่าง:

memorization[i] = min( memorization[i], memorization[i+1]) + A[k][i];

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int getMinSum(vector> &arr) {
    int memorization[arr.size()];
    int n = arr.size() - 1;
    for (int i = 0; i < arr[n].size(); ++i) {
        memorization[i] = arr[n][i];
    }
    for (int i = arr.size() - 2; i >= 0; --i) {
        for (int j = 0; j < arr[i + 1].size() - 1; ++j) {
            memorization[j] = arr[i][j] + min(memorization[j], memorization[j + 1]);
        }
    }
    return memorization[0];
}

int main() {
    vector> arr = {
        {5},
        {7, 3},
        {8, 1, 2},
        {9, 6, 4, 5},
    };
    cout << "Minimum sum path = " << getMinSum(arr) << endl;
    return 0;
}

ผลลัพธ์

Minimum sum path = 13