ผลรวมเส้นทางตกต่ำสุดในกริด NxN ใน C++

ข้อกำหนดโจทย์

• กำหนดเมทริกซ์ A ของจำนวนเต็มขนาด NxN งานคือหาผลรวมต่ำสุดของเส้นทางตกผ่าน A
• เส้นทางตกจะเริ่มที่องค์ประกอบใดก็ได้ในแถวแรกและจบในแถวสุดท้าย
• มันเลือกองค์ประกอบหนึ่งจากแถวถัดไป ตัวเลือกของแถวถัดไปต้องอยู่ในคอลัมน์ที่ต่างจากคอลัมน์ของแถวก่อนหน้าสูงสุด 1

ตัวอย่าง

ถ้า N = 2 และเมทริกซ์คือ: { {5, 10}, {25, 15} } ผลลัพธ์จะเป็น 20 เนื่องจากเลือกองค์ประกอบ 5 และ 15

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

#include <bits/stdc++.h>
#define MAX 2
using namespace std;
int getMinSumPath(int matrix[MAX][MAX]) {
  for (int row = MAX - 2; row >= 0; --row) {
    for (int col = 0; col < MAX; ++col) {
      int val = matrix[row + 1][col];
      if (col > 0) {
        val = min(val, matrix[row +1][col - 1]);
      }
      if (col + 1 < MAX) {
        val = min(val, matrix[row +1][col + 1]);
      }
      matrix[row][col] = matrix[row][col] + val;
    }
  }
  int result = INT_MAX;
  for (int i = 0; i < MAX; ++i)
    result = min(result, matrix[0][i]);
  return result;
}
int main() {
  int matrix[MAX][MAX] = {
    {5, 10},
    {25, 15},
  };
  cout << "Minimum sum path = " << getMinSumPath(matrix) << endl;
  return 0;
}

เมื่อคุณคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

Minimum sum path = 20