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

Cho ma trận vuông arr. Đường đi rơi với dịch chuyển khác 0: chọn đúng 1 phần tử mỗi hàng, 2 hàng liên tiếp không cùng cột. Tìm tổng nhỏ nhất của đường đi như vậy.

Ví dụ: arr = [[1,2,3],[4,5,6],[7,8,9]] → 13. Đường đi [1,5,7] có tổng nhỏ nhất.

Giải pháp

DP bottom-up tối ưu O(n*m):

• Duyệt hàng từ 1 đến n-1
• Tính leftMin[j] = min(arr[i-1][0..j])
• Tính rightMin[j] = min(arr[i-1][j..m-1])
• Với mỗi cột j: leftVal = leftMin[j-1] (hoặc INF), rightVal = rightMin[j+1] (hoặc INF)
• arr[i][j] += min(leftVal, rightVal)
• Kết quả: min của hàng cuối

Tránh chọn cùng cột bằng cách lấy min từ trái/phải trừ cột hiện tại.

Ví dụ mã C++

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

int dp[10005][205]; 

class Solution { 
public: 
    void pre() { 
        for(int i = 0; i <= 10000; i++) 
            for(int j = 0; j <= 204; j++) 
                dp[i][j] = -1; 
    } 
    
    int minFallingPathSum(vector<vector<int>>& arr) { 
        int n = arr.size(); 
        int m = arr[0].size(); 
        
        for (int i = 1; i < n; i++) { 
            vector<int> leftMin(m), rightMin(m); 
            leftMin[0] = arr[i-1][0]; 
            for (int j = 1; j < m; j++) 
                leftMin[j] = min(leftMin[j-1], arr[i-1][j]); 
            
            rightMin[m-1] = arr[i-1][m-1]; 
            for (int j = m-2; j >= 0; j--) 
                rightMin[j] = min(arr[i-1][j], rightMin[j+1]); 
            
            for (int j = 0; j < m; j++) { 
                int leftVal = (j-1 >= 0) ? leftMin[j-1] : 1000000; 
                int rightVal = (j+1 < m) ? rightMin[j+1] : 1000000; 
                arr[i][j] += min(leftVal, rightVal); 
            } 
        } 
        
        int ans = INT_MAX; 
        for (int i = 0; i < m; i++) 
            ans = min(ans, arr[n-1][i]); 
        return ans; 
    } 
}; 

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

Đầu vào

{{1,2,3},{4,5,6},{7,8,9}}

Đầu ra

13