Tổng nhỏ nhất đường đi rơi trong lưới NxN trong C++

Đề bài

• Cho ma trận A các số nguyên kích thước NxN. Nhiệm vụ là tìm tổng nhỏ nhất của đường đi rơi qua A.
• Đường đi rơi sẽ bắt đầu tại 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 hàng tiếp theo phải ở cột khác với cột hàng trước đó tối đa 1 đơn vị.

Ví dụ

Nếu N = 2 và ma trận là:
{ 
    {5, 10},
    {25, 15}
} thì đầu ra sẽ là 20 vì chọn phần tử 5 và 15

Ví dụ mã 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 << "Tổng đường đi nhỏ nhất = " << getMinSumPath(matrix) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Tổng đường đi nhỏ nhất = 20