अनन्य पथ लीटकोड सोल्यूशन


अडचण पातळी मध्यम
वारंवार विचारले अडोब ऍमेझॉन सफरचंद ब्लूमबर्ग बाइट डान्स फेसबुक गोल्डमन Sachs Google गणिते मायक्रोसॉफ्ट ओरॅकल गुण सेल्सबॉल्स Snapchat उबेर व्हीएमवेअर वॉलमार्ट लॅब
अरे डायनॅमिक प्रोग्रामिंग

अनन्य पथ लीटकोड सोल्यूशनमध्ये असे म्हटले आहे की आपल्याला ग्रीडच्या आकाराचे प्रतिनिधित्व करणारे दोन पूर्णांक दिले आहेत. चा आकार वापरुन ग्रीड, ग्रीडची लांबी आणि रुंदी. आम्हाला ग्रीडच्या डाव्या कोप from्यापासून डाव्या कोप from्यापासून उजव्या कोप to्यापर्यंतच्या अद्वितीय पथांची संख्या शोधणे आवश्यक आहे. हालचालींच्या दिशेने आणखी एक अडचण आहे, कोणत्याही वेळी कोणत्याही व्यक्ती खाली किंवा उजवीकडे एकाच दिशेने जाऊ शकते.

उदाहरण

row: 2, column: 2
2

स्पष्टीकरणः कार्य पूर्ण करण्यासाठी केवळ दोन मार्ग आहेत. प्रथम एकतर आपण उजवीकडे किंवा खाली जा. आपण उजवीकडे हलविले तर आपण फक्त खाली हलवू शकता. जर आपण खाली गेले असाल तर आपण फक्त खाली दिशेने जाऊ शकता. तर, केवळ 2 मार्ग शक्य आहेत.

अनन्य पथ लीटकोड सोल्यूशन

row: 2, column: 3
3

स्पष्टीकरणः गंतव्यस्थानावर जाण्यासाठी 6 मार्ग आहेत. आपण उजवीकडे गेले असल्यास विचारात घ्या, तर वरील समस्येस समस्या कमी केली गेली आहे आणि आपल्याकडे उजव्या कोपर्यात जाण्यासाठी 2 मार्ग आहेत. जर आपणास खाली उतरायचे असेल तर, मग उजवीकडे कोपर्यात जाण्यासाठी आपल्याकडे एकच मार्ग आहे. अशा प्रकारे, शेवटपर्यंत पोहोचण्याचे एकूण मार्ग 3 आहेत.

लीटकोड सोल्यूशनसाठी अनन्य मार्गांसाठी ब्रूट फोर्स अ‍ॅप्रोच

अनन्य पथ लीटकोड सोल्यूशनची पुनरावृत्ती सोडविली जाऊ शकते. जसे आपण दुसर्‍या उदाहरणात केले, जिथे आम्ही दिलेली समस्या 2 सबप्रोब्लम्समध्ये कमी केली. या निराकरणात आपण काय करू तेच. एकदा, आम्ही उजवीकडे गेलो, नंतर समस्या कमी होण्यास सबप्रोब्लम (पंक्ती, स्तंभ -1) होते. जर आम्ही खाली दिशेने सरकलो असेल तर समस्या कमी होईल (पंक्ती -1, स्तंभ). आम्ही हे रिकर्सिव सोल्यूशन सहजपणे कोड करू शकतो. परंतु ही कालावधी मर्यादेपेक्षा जास्त होईल कारण समाधान अत्यंत अकार्यक्षम आहे.

ब्रूट फोर्स अप्रोचसाठी कोड

सी ++ कोड

#include <bits/stdc++.h>
using namespace std;

int uniquePaths(int m, int n) {
    if(n==1 || m==1)return 1;
    return uniquePaths(m-1, n) + uniquePaths(m, n-1);
}

int main(){
    cout<<uniquePaths(2, 2);
}
2

जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }
    
    public static void main(String[] args){
    	System.out.print(uniquePaths(2,2));
    }
}
2

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (2 ^ कमाल (मी, एन)), रिकर्सिव्ह फंक्शनमुळे घातांकीय वेळ गुंतागुंत.

स्पेस कॉम्प्लेक्सिटी

ओ (कमाल (मी, एन), कंपाईलर स्टॅकद्वारे वापरलेली जागा. हे रिकर्सिव झाडाच्या उंचीवर अवलंबून असते.

डायनॅमिक प्रोग्रामिंग दृष्टीकोन

रिकर्सिव्ह सोल्यूशनच्या खाली वर स्पष्ट केलेला दृष्टिकोन सहज लक्षात ठेवता येतो. रिकर्सिव फंक्शन रो आणि कॉलम असलेल्या दोन व्हेरिएबल्सवर अवलंबून आहे. अशा प्रकारे आपण 2 डी डीपी तयार करतो अॅरे आणि प्रत्येक राज्याचा निकाल संग्रहित करा. हे वेळेची जटिलता नाटकीयरित्या सुधारेल कारण आम्ही समान समस्या सोडवत नाही.

युनिक पथ लीटकोड सोल्यूशनसाठी डायनॅमिक प्रोग्रामिंग कोड

सी ++ कोड

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> dp;
int uniquePathsUtil(int m, int n) {
    if(m == 1 || n == 1) return 1;
    if(dp[m][n] != -1)
        return dp[m][n];
    return dp[m][n] = uniquePathsUtil(m-1, n) + uniquePathsUtil(m, n-1);
}

int uniquePaths(int m, int n) {
    dp.clear();
    dp.assign(m+1, vector<int>(n+1, -1));
    return uniquePathsUtil(m, n);
}

int main(){
    cout<<uniquePaths(2, 2);
}
2

जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    private static int uniquePathsUtil(int m, int n, int[][] dp) {
        if(m == 1 || n == 1) return 1;
        if(dp[m][n] != 0)
            return dp[m][n];
        return dp[m][n] = uniquePathsUtil(m-1, n, dp) + uniquePathsUtil(m, n-1, dp);
    }

    private static int uniquePaths(int m, int n) {
        int dp[][] = new int[m+1][n+1];
        return uniquePathsUtil(m, n, dp);
    }
    
    public static void main(String[] args){
    	System.out.print(uniquePaths(2,2));
    }
}
2

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * एम), जेथे ग्रॅममधील पंक्ती आणि स्तंभांची संख्या दर्शविण्यासाठी एन, एम वापरले जातात. एकूण एन * एम राज्ये असल्याने, वेळ जटिलता देखील ओ (एन * एम) आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (एन * एम), 2 डी डीपी टेबल तयार करण्यासाठी आवश्यक जागा. डीपी पध्दतीसाठी स्पेस कॉम्प्लेक्सिटी बहुपद आहे.