हमें गैर-नकारात्मक पूर्णांकों की एक सरणी दी गई है जो उस तत्व से आगे किए जा सकने वाले अधिकतम चरणों की संख्या को दर्शाती है। पॉइंटर प्रारंभ में सरणी के पहले इंडेक्स [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("सरणी का आकार दर्ज करें: ");
scanf("%d", &n);
printf("सरणी में तत्व दर्ज करें: ");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("न्यूनतम चरणों की संख्या: %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
