અનન્ય પાથ લીટકોડ સોલ્યુશન


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બ્લૂમબર્ગ ByteDance ફેસબુક ગોલ્ડમૅન સૅશ Google ગણિત માઈક્રોસોફ્ટ ઓરેકલ ક્વોલિટિક્સ Salesforce Snapchat ઉબેર વીએમવેર વોલમાર્ટ લેબ્સ
અરે ડાયનેમિક પ્રોગ્રામિંગ

સમસ્યા અનન્ય પાથ લીટકોડ સોલ્યુશન જણાવે છે કે તમને ગ્રીડના કદને રજૂ કરતા બે પૂર્ણાંકો આપવામાં આવે છે. ના કદનો ઉપયોગ કરીને ગ્રિડ, ગ્રીડની લંબાઈ અને પહોળાઈ. આપણે ગ્રીડના ઉપર ડાબા ખૂણાથી નીચે જમણા ખૂણા સુધીના અનન્ય પાથની સંખ્યા શોધવાની જરૂર છે. ચળવળની દિશા પર એક અન્ય અવરોધ છે, કોઈપણ સમયે, વ્યક્તિ ફક્ત નીચે અથવા જમણી દિશામાં જ આગળ વધી શકે છે.

ઉદાહરણ

row: 2, column: 2
2

સમજૂતી: કાર્ય પૂર્ણ કરવા માટે ફક્ત બે જ રસ્તાઓ છે. પહેલા કાં તો તમે જમણે અથવા નીચે જાઓ. જો તમે જમણે ખસેડ્યા છો તો તમે ફક્ત નીચે જઇ શકો છો. જો તમે નીચે ખસેડ્યા હોત, તો પછી તમે ફક્ત નીચેની દિશામાં જ આગળ વધી શકો છો. તેથી, ફક્ત 2 રસ્તાઓ શક્ય છે.

અનન્ય પાથ લીટકોડ સોલ્યુશન

row: 2, column: 3
3

સમજૂતી: લક્ષ્ય સુધી પહોંચવાની 6 રીત છે. ધ્યાનમાં લો કે જો તમે જમણી તરફ ગયા છો, તો પછી સમસ્યા ઉપરના ઉદાહરણમાં ઓછી થઈ ગઈ છે અને તમારી પાસે જમણા ખૂણાની નીચે પહોંચવાની 2 રીત છે. જો તમારી પાસે નીચે હોત, તો તમારી પાસે નીચે જમણા ખૂણા સુધી પહોંચવાની એકમાત્ર રીત છે. આમ, અંત સુધી પહોંચવાની કુલ રીતોની સંખ્યા 3 છે.

અનન્ય પાથ લીટકોડ સોલ્યુશન માટે બ્રુટ ફોર્સ અભિગમ

સમસ્યા અનન્ય પાથ લીટકોડ સોલ્યુશનને વારંવાર ઉકેલી શકાય છે. જેમ આપણે બીજા ઉદાહરણમાં કર્યું છે, જ્યાં અમે આપેલી સમસ્યાને 2 પેટાપ્રૂબલ્સમાં ઘટાડી છે. આ જ બાબત એ છે કે આપણે આ ઉકેલમાં શું કરીશું. એકવાર, અમે જમણી તરફ વળીએ, પછી સમસ્યા સબપ્રbleબ્લેમ (પંક્તિ, ક columnલમ -1) માં ઘટાડો થાય છે. જો આપણે નીચેની દિશામાં આગળ વધ્યા હોત, તો સમસ્યા ઓછી થઈ (પંક્તિ -1, ક columnલમ). અમે આ રિકરિવ સોલ્યુશનને સરળતાથી કોડ કરી શકીએ છીએ. પરંતુ આ સમય મર્યાદાને ઓળંગી જશે કારણ કે ઉકેલો અત્યંત બિનકાર્યક્ષમ છે.

બ્રુટ ફોર્સ અભિગમ માટેનો કોડ

સી ++ કોડ

#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 ^ મહત્તમ (મી, એન)), પુનરાવર્તિત કાર્યને કારણે ઘાતક સમય જટિલતાને કારણે.

અવકાશ જટિલતા

ઓ (મહત્તમ (મી, એન), કમ્પાઇલર સ્ટેક દ્વારા વપરાયેલી જગ્યા. આ પુનરાવર્તિત વૃક્ષની .ંચાઈ પર આધારિત છે.

ગતિશીલ પ્રોગ્રામિંગ અભિગમ

રિકર્સીવ સોલ્યુશન હેઠળ ઉપર જે અભિગમ સમજાવ્યો છે તે સરળતાથી યાદ કરી શકાય છે. કારણ કે રિકર્સીવ ફંક્શન બે વેરીએબલો પર આધારીત છે જે પંક્તિ અને ક andલમ છે. આમ આપણે 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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન * એમ), જ્યાં એન, એમ નો ઉપયોગ પંક્તિઓની સંખ્યા અને ગ્રીડમાં ક colલમ રજૂ કરવા માટે થાય છે. ત્યાં કુલ એન * એમ રાજ્યો છે, તેથી સમય જટિલતા પણ ઓ (એન * એમ) છે.

અવકાશ જટિલતા

ઓ (એન * એમ), જરૂરી જગ્યા 2D ડીપી ટેબલ બનાવવા માટે છે. ડીપી અભિગમ માટે અવકાશ જટિલતા બહુપદી છે.