Đường giảm tổng nhỏ nhất trong lưới NxN trong C ++

Tuyên bố vấn đề

• Cho ma trận A gồm các số nguyên có kích thước NxN. Nhiệm vụ là tìm tổng nhỏ nhất của đường đi xuống qua A.
• Đường đi xuống sẽ bắt đầu từ bất kỳ phần tử nào trong hàng đầu tiên và kết thúc ở hàng cuối cùng.
• Nó chọn một phần tử từ mỗi hàng tiếp theo. Lựa chọn của hàng tiếp theo phải nằm trong cột khác với cột của hàng trước đó nhiều nhất là cột

Ví dụ

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

Ví dụ

#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;
}

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau

Đầu ra

Minimum sum path = 20