Maximum Path Sum in a Triangle: ผลรวมเส้นทางสูงสุดในสามเหลี่ยมใน C++

ปัญหา

กำหนดตัวเลขเรียงเป็น Triangle (แถวแรก 1 ตัว, เพิ่มทีละ 1 จน n ตัว) หา Maximum Path Sum จากยอดลงฐาน เคลื่อนที่ได้ซ้าย-ล่างหรือขวา-ล่าง

ตัวอย่าง:

   1
  5 6
 8 2 9

แนวคิด: Dynamic Programming (Bottom-Up)

แปลงเป็น Matrix (Left-Aligned + Zero Padding)

1 0 0
5 6 0
8 2 9

DP Transition

for i = n-2 downto 0:
    for j = 0 to i:
        mat[i][j] += max(mat[i+1][j], mat[i+1][j+1]);

mat[0][0] จะเป็นคำตอบ

โค้ด C++

#include <iostream>
#include <algorithm>
using namespace std;

#define N 3

int findMaxPathSumTriangle(int mat[][N], int m, int n) {
    for (int i = m - 1; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            if (mat[i+1][j] > mat[i+1][j+1]) {
                mat[i][j] += mat[i+1][j];
            } else {
                mat[i][j] += mat[i+1][j+1];
            }
        }
    }
    return mat[0][0];
}

int main() {
    int triangle[N][N] = {
        {1, 0, 0},
        {5, 6, 0},
        {8, 2, 9}
    };
    cout << "The maximum path sum in triangle is " << findMaxPathSumTriangle(triangle, 2, 2);
    return 0;
}

การทำงานตัวอย่าง

Initial:
1 0 0
5 6 0
8 2 9

Row 1 (i=1):
j=0: 5 + max(8,2) = 13
j=1: 6 + max(2,9) = 15
Matrix:
1  0  0
13 15 0
8  2  9

Row 0 (i=0):
j=0: 1 + max(13,15) = 16
Result: 16

ความซับซ้อน

• Time: O(n²)
• Space: O(1) Extra (In-place)

Input / Output

Input:  Triangle 3 rows
Output: The maximum path sum in triangle is 16