न्यूनतम जंप्स समस्या

इस समस्या में, धनात्मक पूर्णांकों की एक सूची दी गई है। प्रत्येक पूर्णांक दर्शाता है कि वर्तमान तत्व से अधिकतम कितने कदम उठाए जा सकते हैं। पहले तत्व से शुरू करके, हमें सूची के अंतिम आइटम तक पहुंचने के लिए न्यूनतम जंप्स की संख्या ढूंढनी है।

डायनामिक प्रोग्रामिंग दृष्टिकोण के लिए, एक jumps ऐरे परिभाषित किया जाता है जो आवश्यक न्यूनतम जंप्स को स्टोर करता है। जैसे jumps[i] के मान के लिए, यह दर्शाता है कि 0वें इंडेक्स से ऐरे के ith इंडेक्स तक पहुंचने के लिए कितने न्यूनतम जंप्स आवश्यक हैं।

इनपुट और आउटपुट

इनपुट: पूर्णांकों की एक सूची
{1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}

आउटपुट: अंतिम स्थान तक पहुंचने के लिए न्यूनतम जंप्स की संख्या। यह 3 है।
मान 1 से शुरू करें, 3 पर जाएं। फिर 3 मान कूदकर 8 पर पहुंचें। फिर 8 मान कूदकर अंतिम तत्व पर पहुंचें।

एल्गोरिदम

minPossibleJump(list, n)

इनपुट: संख्या ऐरे, ऐरे में तत्वों की संख्या
आउटपुट: अंत तक पहुंचने के लिए आवश्यक न्यूनतम जंप्स की संख्या

शुरुआत
    jump नामक ऐरे को आकार n का परिभाषित करें
    यदि n = 0 या list[0] = 0, तो
        वापस ∞
    jump[0] := 0
    i := 1 से n तक, करें
        jumps[i] := ∞
        j := 0 से i तक, करें
            यदि i <= j + list[j] और jump[j] ≠ ∞, तो
                jump[i] := jump[i] और (jump[j] + 1) का न्यूनतम
                लूप तोड़ें
        पूर्ण
    पूर्ण
    वापस jump[n-1]
अंत

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

int min(int x, int y) {
    return (x < y) ? x : y;
}

int minPossibleJump(int list[], int n) {
    int *jumps = new int[n];
    
    if (n == 0 || list[0] == 0)
        return INT_MAX;
    
    jumps[0] = 0;
    for (int i = 1; i < n; i++) {
        jumps[i] = INT_MAX;
        for (int j = 0; j < i; j++) {
            if (i <= j + list[j] && jumps[j] != INT_MAX) {
                jumps[i] = min(jumps[i], jumps[j] + 1);
                break;
            }
        }
    }
    return jumps[n-1];
}

int main() {
    int list[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
    int size = 11;
    cout << "Minimum number of jumps to reach end is: " << minPossibleJump(list, size);
    return 0;
}

आउटपुट

Minimum number of jumps to reach end is: 3