C++ এ গেম ভি জাম্প করুন

ধরুন আমাদের কাছে পূর্ণসংখ্যার একটি অ্যারে আছে যাকে বলা হয় arr এবং একটি পূর্ণসংখ্যা d। এক ধাপে আমরা সূচক i থেকে −

• i + x যেখানে:i + x

• i - x যেখানে:i - x>=0 এবং x 1 থেকে d পর্যন্ত।

এখানে n হল অ্যারের আকার। উপরন্তু, আমরা শুধুমাত্র i এবং j-এর মধ্যে সমস্ত সূচক k-এর জন্য arr[i]> arr[j] এবং arr[i]> arr[k] সূচক i থেকে j তে যেতে পারি। আমরা অ্যারের যেকোনো সূচক বেছে নিতে পারি এবং জাম্পিং শুরু করতে পারি। আমরা পরিদর্শন করতে পারি এমন সর্বাধিক সংখ্যক সূচক খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট d =2 এর মত হয় এবং উচ্চতা হয়

তাহলে আউটপুট হবে 4, আমরা ইনডেক্স 10 থেকে শুরু করতে পারি। আমরা ইনডেক্স 10 থেকে লাফ দিতে পারি --> 8 --> 6 --> 7 যেমন দেখানো হয়েছে। তাই যদি আমরা সূচী 6 থেকে শুরু করি তাহলে আমরা শুধুমাত্র 7 সূচকে যেতে পারি। আমরা সূচক 5 এ যেতে পারি না কারণ 13> 9। আমরা সূচক 4 এ যেতে পারি না কারণ সূচক 5 সূচক 4 এবং 6 এবং 13> 9 এর মধ্যে। এবং এছাড়াও, আমরা সূচী 3 থেকে সূচী 2 বা সূচক 1 তে লাফানো যাবে না।

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

• একটি অ্যারে ডিপি

  সংজ্ঞায়িত করুন

• একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এটি একটি অ্যারে অ্যারে, আইডিএক্স, ডি,

  নেবে

• যদি dp[idx] -1 এর সমান না হয়, তাহলে −

  • dp[idx]

    ফেরত দিন

• ret :=1

• n :=arr এর আকার

• আরম্ভ করার জন্য i :=idx + 1, যখন i

  • যদি i> idx + d হয়, তাহলে −

    • লুপ থেকে বেরিয়ে আসুন

  • যদি arr[i]>=arr[idx] হয়, তাহলে -

    • লুপ থেকে বেরিয়ে আসুন

  • ret :=ret এর সর্বাধিক এবং 1 + সমাধান(arr, i, d)

• আরম্ভ করার জন্য i :=idx - 1, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), −

  • যদি i

    • লুপ থেকে বেরিয়ে আসুন

  • যদি arr[i]>=arr[idx] হয়, তাহলে -

    • লুপ থেকে বেরিয়ে আসুন

  • ret :=ret এর সর্বাধিক এবং 1 + সমাধান(arr, i, d)

• dp[idx] :=ret

• রিটার্ন রিটার্ন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• n :=arr এর আকার

• dp :=n আকারের একটি অ্যারে নির্ধারণ করুন এবং এটি -1

  দিয়ে পূরণ করুন

• ret :=1

• আরম্ভ করার জন্য i :=0, যখন i

  • ret :=ret এবং সমাধানের সর্বাধিক (arr, i, d)

• রিটার্ন রিটার্ন

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<int> dp;
   int solve(vector <int>& arr, int idx, int d){
      if (dp[idx] != -1)
      return dp[idx];
      int ret = 1;
      int n = arr.size();
      for (int i = idx + 1; i < n; i++) {
         if (i > idx + d)
         break;
         if (arr[i] >= arr[idx])
         break;
         ret = max(ret, 1 + solve(arr, i, d));
      }
      for (int i = idx - 1; i >= 0; i--) {
         if (i < idx - d)
         break;
         if (arr[i] >= arr[idx])
         break;
         ret = max(ret, 1 + solve(arr, i, d));
      }
      return dp[idx] = ret;
   }
   int maxJumps(vector<int>& arr, int d) {
      int n = arr.size();
      dp = vector<int>(n, -1);
      int ret = 1;
      for (int i = 0; i < n; i++) {
         ret = max(ret, solve(arr, i, d));
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {6,4,14,6,8,13,9,7,10,6,12};
   cout << (ob.maxJumps(v, 2));
}

ইনপুট

{6,4,14,6,8,13,9,7,10,6,12}, 2

আউটপুট

4