Tổng đường đi rơi tối thiểu trong C++

Cho ma trận vuông A. Tìm tổng nhỏ nhất của đường đi "rơi": bắt đầu hàng 0, mỗi bước xuống hàng dưới ở cột cùng hoặc cột liền kề (chênh lệch ≤ 1).

Ví dụ: [[1,2,3],[4,5,6],[7,8,9]] → 12 (đường đi 1→4→7).

Thuật toán giải quyết (DP bottom-up in-place)

1. Duyệt từ hàng倒 số 2 lên hàng 0:
   • Với mỗi cột j: lấy min của 3 ô ở hàng dưới (j-1, j, j+1, coi ngoài biên = ∞).
   • Cập nhật A[i][j] += min.
2. Kết quả = min của hàng 0.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& a) {
        int n = a.size();
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                int x1 = (j > 0) ? a[i+1][j-1] : INT_MAX;
                int x2 = a[i+1][j];
                int x3 = (j + 1 < n) ? a[i+1][j+1] : INT_MAX;
                a[i][j] += min({x1, x2, x3});
            }
        }
        int ans = INT_MAX;
        for (int x : a[0]) ans = min(ans, x);
        return ans;
    }
};

int main() {
    vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
    Solution ob;
    cout << ob.minFallingPathSum(v);
}

Đầu vào

[[1,2,3],[4,5,6],[7,8,9]]

Đầu ra

12