C++-এ জাম্প গেম V (Jump Game V)

ধরি arr নামক একটি ইন্টিজার অ্যারে এবং d নামক একটি ইন্টিজার দেওয়া আছে। এক স্টেপে আমরা ইন্ডেক্স i থেকে যেতে পারি –

i + x যেখানে: i + x < n এবং x হলো 1 থেকে d পরিসরে
i - x যেখানে: i - x >= 0 এবং x হলো 1 থেকে d পরিসরে

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

ইনপুট যদি d = 2 এবং হাইটস হয় –

তাহলে আউটপুট হবে 4, কারণ আমরা ইন্ডেক্স 10 থেকে শুরু করে 10 → 8 → 6 → 7 এ যেতে পারি।

সমাধানের ধাপসমূহ

dp নামক একটি অ্যারে সংজ্ঞায়িত করুন
solve() ফাংশন সংজ্ঞায়িত করুন যা arr, idx, d নেবে –
- যদি dp[idx] != -1 হয়, তবে dp[idx] ফেরত দিন
- ret := 1
- n := arr এর আকার
- i := idx + 1 থেকে n-1 পর্যন্ত লুপ চালান –
  - যদি i > idx + d হয়, তবে ব্রেক করুন
  - যদি arr[i] >= arr[idx] হয়, তবে ব্রেক করুন
  - ret := max(ret, 1 + solve(arr, i, d))
- i := idx - 1 থেকে 0 পর্যন্ত লুপ চালান –
  - যদি i < idx - d হয়, তবে ব্রেক করুন
  - যদি arr[i] >= arr[idx] হয়, তবে ব্রেক করুন
  - ret := max(ret, 1 + solve(arr, i, d))
- dp[idx] := ret
- ret ফেরত দিন
মূল পদ্ধতিতে –
- n := arr এর আকার
- dp := n আকারের অ্যারে -1 দিয়ে ফিল করুন
- ret := 1
- i := 0 থেকে n-1 পর্যন্ত লুপ চালিয়ে ret := max(ret, solve(arr, i, d)) করুন
- ret ফেরত দিন

বेहतर বোঝার জন্য নিচের কোডটি দেখুন –

উদাহরণ

#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