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

Giả sử chúng ta có một mảng vuông các số nguyên A, chúng ta muốn tổng nhỏ nhất của một đường đi xuống thông qua A. Đường đi xuống về cơ bản là một đường bắt đầu từ bất kỳ phần tử nào trong hàng đầu tiên và chọn một phần tử từ mỗi hàng. Và phần tử 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à một. Vì vậy, nếu ma trận giống như -

Khi đó đầu ra là 12. Có vài đường rơi khác nhau. đây là [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9], [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,9], [3,5,7], [3 , 5,8], [3,5,9], [3,6,8], [3,6,9] và đường dẫn tổng nhỏ nhất là [1,4,7] và tổng là 12.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng
• đối với tôi trong phạm vi n - 2 giảm xuống 0
  • cho j trong phạm vi từ 0 đến n
    • nếu j - 1 <0, thì x1:=inf, nếu không thì x1:=matrix [i + 1, j - 1]
    • x2:=ma trận [i + 1, j]
    • nếu j + 1> =n thì x3:=inf, ngược lại x3:=matrix [i + 1, j + 1]
    • matrix [i, j]:=matrix [i, j] + min of x1, x2, x3
• ans:=inf
• cho tôi trong phạm vi từ 0 đến n - 1
  • ans:=min của ans và ma trận [0, i]
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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-1<0?INT_MAX:a[i+1][j-1];
            int x2 = a[i+1][j];
            int x3 = j+1>=n?INT_MAX:a[i+1][j+1];
            a[i][j]+= min({x1,x2,x3});
         }
      }
      int ans = INT_MAX;
      for(int i =0;i<n;i++){
         ans = min(ans,a[0][i]);
      }
      return ans;
   }
};
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