Maximum Sum Path in Right Number Triangle ใน C++

ปัญหา

มีสามเหลี่ยมจำนวนเต็ม (Right Triangle) หาเส้นทางจากยอดถึงฐานที่ให้ผลรวมสูงสุด เคลื่อนที่ได้แค่ลงตรงหรือลงขวา

ตัวอย่าง

   3
  4 5
 1 10 7
Max Sum = 18 (3+5+10)

อัลกอริทึม (Dynamic Programming In-place)

1. แถวที่ 1: เพิ่มค่าจากแถวบน (มีแค่ทางเดียว)
2. แถว i (i≥2):
   • ขอบซ้าย: triangle[i][0] += triangle[i-1][0]
   • ขอบขวา: triangle[i][i] += triangle[i-1][i-1]
   • กลาง: triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
3. คำตอบ = max ของแถวสุดท้าย

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

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

int maxSum(int tringle[][3], int n){
    if (n > 1) {
        tringle[1][1] += tringle[0][0];
        tringle[1][0] += tringle[0][0];
    }
    for(int i = 2; i < n; i++) {
        tringle[i][0] += tringle[i-1][0];
        tringle[i][i] += tringle[i-1][i-1];
        for (int j = 1; j < i; j++){
            if (tringle[i][j] + tringle[i-1][j-1] >= tringle[i][j] + tringle[i-1][j])
                tringle[i][j] += tringle[i-1][j-1];
            else
                tringle[i][j] += tringle[i-1][j];
        }
    }
    int max = tringle[n-1][0];
    for(int i = 1; i < n; i++)
        if(max < tringle[n-1][i]) max = tringle[n-1][i];
    return max;
}

int main(){
    int tringle[3][3] = {{3}, {4,5}, {1,10,7}};
    cout << "Maximum sum = " << maxSum(tringle, 3) << endl;
    return 0;
}

ผลลัพธ์

Maximum sum = 18