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

ปัญหา

กำหนดตัวเลขเรียงเป็น Inverted Triangle (แถวแรก n ตัว, แถวถัดไป n-1, ... จน 1 ตัว) หา Maximum Path Sum จากแถวล่างสุดขึ้นบนสุด โดยเคลื่อนที่ได้เฉพาะซ้ายหรือขวา

ตัวอย่าง:

5  1  9
 3  6
  2

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

แปลงเป็น Matrix

Shift ซ้าย + เติม 0:

5 1 9
3 6 0
2 0 0

DP Transition

dp[i][j] = Max Sum จาก (i,j) ลงสู่ฐาน

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

โค้ด C++

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

#define N 3

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

int main() {
    int invertedTriangle[N][N] = {
        {5, 1, 9},
        {3, 6, 0},
        {2, 0, 0}
    };
    cout << "The maximum path sum is " << findMaxPathSumInvertedTriangle(invertedTriangle);
    return 0;
}

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

Initial:
5 1 9
3 6 0
2 0 0

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

Row 0 (i=0):
j=0: 5 + max(5,0) = 10
j=1: 1 + max(8,5) = 9
j=2: 9 + max(0,8) = 17  ← MAX!
Result: 17

ความซับซ้อน

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

Input / Output

Input:  Inverted triangle 3 rows
Output: The maximum path sum is 17