আমাদের একটি অ্যারে দেওয়া আছে নন-নেগেটিভ ইন্টিজার (non-negative integers) দিয়ে, যা প্রতিটি এলিমেন্ট থেকে maksimাম কতটি ধাপ অগ্রে যাওয়া যায় তা নির্দেশ করে। পয়েন্টারটি প্রাথমিক অবস্থায় অ্যারের প্রথম ইনডেক্স [0 index]-এ থাকে। আপনার লক্ষ্য হল অ্যারের লাস্ট ইনডেক্স-এ ন্যূনতম ধাপে পৌঁছানো। যদি অ্যারের শেষে পৌঁছানো সম্ভব না হয়, তবে ম্যাক্সিমাম ইন্টিজার প্রিন্ট করা।
নেইভ অ্যাপ্রোচ (naive approach) হল প্রথম এলিমেন্ট থেকে শুরু করে রিকার্সিভলি (recursively) প্রথম এলিমেন্ট থেকে অ্যাক্সেসিবল (accessible) সব এলিমেন্টের জন্য কল করা। প্রথম এলিমেন্ট থেকে এন্ডে পৌঁছানোর মিনিমাম জাম্প সংখ্যা, প্রথম এলিমেন্ট থেকে অ্যাক্সেসিবল এলিমেন্টগুলোর থেকে এন্ডে পৌঁছানোর মিনিমাম জাম্প ব্যবহার করে ক্যালকুলেট করা হয়।
minJumps(start, end) = Min( minJumps(k, end) ) for all k accessible from the start
এখানে আমরা ডাইনামিক প্রোগ্রামিং-এর টপ-ডাউন (top-down) অ্যাপ্রোচ ব্যবহার করব। আমরা হ্যাশম্যাপ (Hashmap) ব্যবহার করব সাবপ্রোবলেমের রেজাল্ট স্টোর করার জন্য এবং যখনই সমাধান তৈরি করব, প্রথমে চেক করব সাবপ্রোবলেমটি ইতিমধ্যে সমাধান হয়েছে কিনা, হ্যাঁ হলে সেটি ব্যবহার করব।
Input: {1, 2, 4, 1, 2, 2, 1, 1, 3, 8}
Output: Minimum number of steps = 6 {1→2→4→1→3→8}
ব্যাখ্যা (Explanation)
প্রথম এলিমেন্ট হল ১, তাই এটি শুধু ২-তে যেতে পারে। দ্বিতীয় এলিমেন্ট হল ২, তাই এটি সর্বোচ্চ ২ ধাপ নিতে পারে (যেমন ৪ বা ১)। এটি ৪-এ যেতে পারে যেখানে থেকে ১-এ পৌঁছায় এবং এভাবে চলতে থাকে।
ডাইনামিক প্রোগ্রামিং অ্যাপ্রোচ দিয়ে অ্যারের শেষে পৌঁছানোর মিনিমাম জাম্প বের করার কমপ্লেক্সিটি O(n²) স্পেস কমপ্লেক্সিটি O(n)।
উদাহরণ (C প্রোগ্রাম)
#include <stdio.h>
#include <limits.h>
int min_steps(int arr[], int n) {
int steps[n];
int i, j;
if (n == 0 || arr[0] == 0)
return INT_MAX;
steps[0] = 0;
for (i = 1; i < n; i++) {
steps[i] = INT_MAX;
for (j = 0; j < i; j++) {
if (i <= j + arr[j] && steps[j] != INT_MAX) {
steps[i] = (steps[i] < (steps[j] + 1)) ? steps[i] : steps[j] + 1;
break;
}
}
}
return steps[n - 1];
}
int main() {
int arr[100];
int n;
printf("Enter size of the array: ");
scanf("%d", &n);
printf("Enter elements in the array: ");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Minimum number of steps: %d", min_steps(arr, n));
return 0;
}
আউটপুট
Enter size of array: 7 Enter elements in the array: 2 1 1 5 2 1 1 Minimum number of steps: 3
ব্যাখ্যা: DP টেবিল steps[] এ প্রতিটি ইনডেক্সে সেখানে পৌঁছানোর মিনিমাম জাম্প স্টোর করা হয়। ইনার লুপে ব্রেক (break) ব্যবহার করা হয়েছে যা কিছুটা অপ্টিমাইজেশন, কিন্তু সঠিক লজিকের জন্য সব j চেক করা উচিত ছিল। এটি O(n²) টাইম কমপ্লেক্সিটি দেয়।
