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

คำชี้แจงปัญหา

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

ตัวอย่าง

If N = 2 and matrix is:
{
   {5, 10},
   {25, 15}
} then output will be 20 as element 5 and 15 are selected

ตัวอย่าง

#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