हमें दिए गए हैं, गैर-ऋणात्मक पूर्णांकों की एक सरणी जो उस तत्व से आगे बढ़ने वाले चरणों की अधिकतम संख्या को दर्शाती है। सूचक प्रारंभ में सरणी के पहले अनुक्रमणिका [0 अनुक्रमणिका] पर स्थित है। आपका लक्ष्य न्यूनतम चरणों में सरणी के अंतिम सूचकांक तक पहुंचना है। यदि सरणी के अंत तक पहुंचना संभव नहीं है तो अधिकतम पूर्णांक प्रिंट करें।
निष्पक्ष दृष्टिकोण प्रारंभिक {प्राथमिक} घटक से शुरू करना है और पहले तत्व से सुलभ सभी घटकों के लिए पुनरावर्ती कॉल करना है। पहले से अंत तक पहुंचने के लिए कूदने की न्यूनतम सीमा की गणना पहले से पहुंच योग्य तत्वों से अंत प्राप्त करने के लिए आवश्यक कूद की न्यूनतम सीमा का उपयोग करके की जाती है।
minJumps(start, end) = Min ( minJumps(k, end) ) for all k accessible from the start
यहां हम डायनेमिक प्रोग्रामिंग के टॉप-डाउन अप्रोच का उपयोग करेंगे। हम उप-समस्या के परिणामों को संग्रहीत करने के लिए हैशमैप का उपयोग करेंगे और जब भी हम कोई समाधान बनाएंगे, तो पहले जांच लें कि क्या उप-समस्या पहले ही हल हो चुकी है, यदि हां, तो इसका उपयोग करें।
Input: { 1, 2, 4, 1, 2, 2, 1, 1, 3, 8 }
Output: Minimum number of steps = 6 {1-->2-->4-->1-->3-->8} स्पष्टीकरण
पहला तत्व 1 है, इसलिए यह केवल 2 पर जा सकता है। दूसरा तत्व 2 है, इसलिए अधिकतम 2 चरण बना सकता है जैसे 4 या 1। यह 4 तक जाता है जहां से यह 1 तक पहुंचता है और इसी तरह।
एक सरणी के अंत तक पहुंचने के लिए न्यूनतम संख्या में छलांग लगाने के लिए गतिशील प्रोग्रामिंग दृष्टिकोण की जटिलता O(n^2) है जिसमें O(n) की अंतरिक्ष जटिलता है
उदाहरण
#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