अद्वितीय पथ Leetcode समाधान


कठिनाई तह मध्यम
बारम्बार सोधिन्छ एडोब अमेजन एप्पल ब्लूमबर्ग बाइटडेन्स फेसबुक Goldman सैक्स गुगल गणित माइक्रोसफ्ट बजेट क्वालिट्रिक्स SalesForce Snapchat Uber VMware वालमार्ट ल्याबहरू
एरे डायनामिक प्रोग्रामिंग

समस्या अद्वितीय पथ Leetcode समाधान भन्छ कि तपाईंलाई दुई इन्टिजर दिइन्छ ग्रिडको आकार प्रतिनिधित्व गर्दछ। को आकार प्रयोग गर्दै ग्रिड, ग्रिडको लम्बाई र चौड़ाई। हामीले ग्रिडको शीर्ष बायाँ कुनामा देखि तल दायाँ कुनामा अद्वितीय पथहरूको संख्या फेला पार्न आवश्यक छ। आन्दोलनको दिशामा त्यहाँ अर्को अवरोध छ, कुनै पनि समय, एक या त तल वा दायाँ दिशामा मात्र सर्न सक्छ।

उदाहरणका

row: 2, column: 2
2

स्पष्टीकरण: कार्य पूरा गर्न केवल दुई तरिकाहरू छन्। पहिले कि त तपाईं दायाँ वा तल सार्नुहोस्। यदि तपाईं सहि सारिनुभयो भने तपाईं मात्र तल सार्न सक्नुहुन्छ। यदि तपाईं तल सारिनु भएको थियो भने, तपाईं मात्र तल दिशा मा सार्न सक्नुहुन्छ। त्यसो भए, केवल २ तरिकाहरू सम्भव छन्।

अद्वितीय पथ Leetcode समाधान

row: 2, column: 3
3

स्पष्टीकरण: गन्तव्यमा पुग्न ways तरिकाहरू छन्। विचार गर्नुहोस् यदि तपाईं दायाँ जानुभएको छ भने, तब समस्या माथिको उदाहरणमा कम गरिएको छ र तपाईंसँग दायाँ कुनामा दायाँ पुग्ने २ तरिकाहरू छन्। यदि तपाईं तल हुनुहुन्थ्यो भने, तपाईं तल तल दायाँ कुनामा पुग्ने एकल तरीका छ। यसैले, अन्त्यमा पुग्न मार्गहरूको कुल संख्या is हो।

विचित्र पथ Leetcode समाधानको लागि ब्रुट फोर्स दृष्टिकोण

समस्या अद्वितीय पथ Leetcode समाधान पुनरावृत्ति रूपमा समाधान गर्न सकिन्छ। जसरी हामीले दोस्रो उदाहरणमा गर्‍यौं, जहाँ हामीले दिइएको समस्यालाई २ सबप्रोब्लम्समा कम गर्यौं। उही चीज यो हो कि हामी यस समाधानमा के गर्छौं। एकचोटि, हामी दायाँ सर्छौं, त्यसपछि समस्या उप-समस्या (प row्क्ति, स्तम्भ -१) मा कम भयो। यदि हामी तलको दिशामा सरेका थियौं भने, समस्या (पंक्ति -१, स्तम्भ) मा कम भयो। हामी सजिलैसँग यो रिकर्सिव समाधान कोड गर्न सक्छौं। तर यो समय सीमा भन्दा बढी हुनेछ किनभने समाधान अत्यन्त असक्षम छ।

ब्रूट फोर्स अप्रोचको लागि कोड

C ++ कोड

#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

जटिलता विश्लेषण

समय जटिलता

O (२ ^ अधिकतम (m, n)), कारण रिकर्सिभ प्रकार्यका कारण एक्सपोन्शियल समय जटिलता।

ठाउँ जटिलता

O (अधिकतम (m, n), कम्पाइलर स्ट्याकले प्रयोग गरेको खाली ठाउँ। यो रिकर्सिभ रूखको उचाईमा निर्भर गर्दछ।

गतिशील प्रोग्रामिंग दृष्टिकोण

रिकर्सिव समाधान अन्तर्गत माथि वर्णन गरिएको दृष्टिकोण सजिलैसँग कण्ठ गर्न सकिन्छ। चूंकि रिकर्सिव प्रकार्य दुई चरहरूमा निर्भर गर्दछ जुन प row्क्ति, र स्तम्भ हो। यसैले हामी 2D DP सिर्जना गर्छौं array र प्रत्येक राज्य को नतिजा स्टोर। यसले नाटकीय रूपमा समयको जटिलतामा सुधार ल्याउनेछ किनकि हामी उही समस्याहरूको समाधान गर्दै छैनौं।

गतिशील प्रोग्रामिंग कोड अद्वितीय पथ Leetcode समाधान को लागी

C ++ कोड

#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

जटिलता विश्लेषण

समय जटिलता

O (N * M), जहाँ N, M लाई प r्क्तिहरूको संख्या, र ग्रिडमा स्तम्भहरू प्रतिनिधित्व गर्न प्रयोग गरिन्छ। त्यहाँ जम्मा N * M राज्यहरू छन्, समयको जटिलता O (N * M) पनि हो।

ठाउँ जटिलता

O (N * M), आवश्यक ठाँउ 2D DP तालिका को निर्माण को लागी हो। स्पेस जटिलता डीपी दृष्टिकोणको लागि बहुपद हो।