C++ এ ন্যূনতম ফলিং পাথ যোগফল

ধরুন আমাদের কাছে পূর্ণসংখ্যা A এর একটি বর্গাকার অ্যারে আছে, আমরা A এর মাধ্যমে একটি পতনশীল পথের ন্যূনতম যোগফল চাই। পতনশীল পথটি মূলত একটি পাথ যা প্রথম সারির যেকোনো উপাদান থেকে শুরু হয় এবং প্রতিটি সারি থেকে একটি উপাদান বেছে নেয়। এবং পরবর্তী সারির উপাদানটি এমন একটি কলামে থাকতে হবে যা পূর্ববর্তী সারির কলাম থেকে সর্বাধিক একটি দ্বারা আলাদা। তাই ম্যাট্রিক্স যদি −

এর মত হয়

1	2	3
4	5	6
7	8	9

তারপর আউটপুট হল 12। কয়েকটি ভিন্ন পতনের পথ আছে। এগুলো হল [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], এবং ক্ষুদ্রতম সমষ্টি পথ হল [1,4,7] এবং যোগফল হল 12৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=অ্যারের আকার
আমি n – 2 থেকে 0
উত্তর :=inf
আমি 0 থেকে n – 1
- উত্তর :=উত্তরের সর্বনিম্ন এবং ম্যাট্রিক্স[0, i]
উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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

ইনপুট

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