ন্যূনতম সংখ্যা জাম্পের সমস্যা

এই সমস্যায়, ধনাত্মক পূর্ণসংখ্যার একটি তালিকা দেওয়া হয়েছে। প্রতিটি পূর্ণসংখ্যা নির্দেশ করছে যে বর্তমান উপাদান থেকে কতগুলি সর্বোচ্চ ধাপ তৈরি করা যেতে পারে। প্রথম উপাদান থেকে শুরু করে, তালিকার শেষ আইটেমে পৌঁছানোর জন্য আমাদের ন্যূনতম সংখ্যক লাফ খুঁজে বের করতে হবে।

গতিশীল প্রোগ্রামিং পদ্ধতির জন্য, একটি জাম্প অ্যারে সংজ্ঞায়িত করা হয় যাতে ন্যূনতম সংখ্যক জাম্প প্রয়োজন হয়। লাফের একটি মানের মতন[i], এটি নির্দেশ করে যে 0 তম সূচক থেকে অ্যারের ith সূচকে পৌঁছানোর জন্য কতটি সর্বনিম্ন লাফ প্রয়োজন।

ইনপুট এবং আউটপুট

Input:
A list of integers. {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output:
The minimum number of jumps to reach the end location. It is 3.
Start from value 1, go to 3. then jumps 3 values and reach 8. then jump 8 values and reach the last element.

অ্যালগরিদম

minPossibleJump(list, n)

ইনপুট: সংখ্যা অ্যারে, অ্যারের উপাদানের সংখ্যা।

আউটপুট: শেষ পর্যন্ত পৌঁছানোর জন্য ন্যূনতম সংখ্যক জাম্প প্রয়োজন।

Begin
   define an array named jump of size n
   if n = 0 or list[0] = 0, then
      return ∞
   jump[0] := 0

   for i := 1 to n, do
      jumps[i] := ∞
      for j := 0 to i, do
         if i <= j + list[j] and jump[j] ≠ ∞, then
            jump[i] := minimum of jump[i] and (jump[j] + 1)
            break the loop
      done
   done

   return jump[n-1]
End

উদাহরণ

#include<iostream>
using namespace std;

int min(int x, int y) {
   return (x < y)? x: y;
}

int minPossibleJump(int list[], int n) {
   int *jumps = new int[n];     // dynamically create jumps array to store steps
   if (n == 0 || list[0] == 0)
       return INT_MAX;
   jumps[0] = 0;

   for (int i = 1; i < n; i++) {
      jumps[i] = INT_MAX;    //initially set jumps as infinity
      for (int j = 0; j < i; j++) {
         if (i <= j + list[j] && jumps[j] != INT_MAX) {
            jumps[i] = min(jumps[i], jumps[j] + 1);
            break;
         }
      }
   }
   return jumps[n-1];
}

int main() {
   int list[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
   int size = 11;
   cout << "Minimum number of jumps to reach end is: "<< minPossibleJump(list,size);
   return 0;
}

আউটপুট

Minimum number of jumps to reach end is: 3