জাভাস্ক্রিপ্টে ক্ষুদ্রতম যোগফল সহ পাথ

সমস্যা

জাভাস্ক্রিপ্ট ফাংশন যা প্রথম এবং একমাত্র যুক্তি হিসাবে সংখ্যার 2-ডি অ্যারে নেয়৷

আমাদের ফাংশন প্রতিটি সারি থেকে ঠিক একটি উপাদান বাছাই করে 2-ডি অ্যারে থেকে পাথ খুঁজে বের করা উচিত এবং সন্নিহিত সারি থেকে বাছাই করা দুটি উপাদান একই কলামে থাকা উচিত নয়। এই সমস্ত পথগুলির মধ্যে, আমাদের ফাংশনটি সেই পথের যোগফল ফেরত দেবে যার ন্যূনতম যোগফল রয়েছে৷

উদাহরণস্বরূপ, যদি ফাংশনে ইনপুট হয় −

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

তারপর আউটপুট −

const output = 9;

আউটপুট ব্যাখ্যা

কারণ সমস্ত বৈধ পথ হল −

এবং এই সবগুলির মধ্যে, [1, 2, 6] এর সর্বনিম্ন যোগফল 9।

উদাহরণ

এর জন্য কোড হবে −

const arr = [
   [4, 7, 1],
   [2, 8, 3],
   [5, 6, 9]
]
const minimumPathSum = (arr = []) => {
   let first = [0, null];
   let second = [0, null];
   for(let row = arr.length - 1; row >= 0; row--){
      let curr1 = null;
      let curr2 = null;
      for(let column = 0; column < arr[row].length; column++){
         let currentSum = arr[row][column];
         if(column !== first[1]){
            currentSum += first[0];
         }else{
            currentSum += second[0];
         };
         if(curr1 === null || currentSum < curr1[0]){
            curr2 = curr1;
            curr1 = [currentSum, column];
         }else if(curr2 === null || currentSum < curr2[0]){
            curr2 = [currentSum, column];
         };
      };
      first = curr1;
      second = curr2;
   };
   return first[0];
};
console.log(minimumPathSum(arr));

আউটপুট

এবং কনসোলে আউটপুট হবে −

9