ਵਿਲੱਖਣ ਮਾਰਗ ਲੀਟਕੋਡ ਹੱਲ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਅਡੋਬ ਐਮਾਜ਼ਾਨ ਸੇਬ ਬਲੂਮਬਰਗ ਬਾਈਟਡੈਂਸ ਫੇਸਬੁੱਕ ਗੋਲਡਮੈਨ ਸਾਕਸ ਗੂਗਲ ਗਣਿਤ Microsoft ਦੇ ਓਰੇਕਲ ਗੁਣਾਤਮਕ Salesforce Snapchat ਉਬੇਰ VMware ਵਾਲਮਾਰਟ ਲੈਬ
ਅਰੇ ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ

ਸਮੱਸਿਆ ਵਿਲੱਖਣ ਮਾਰਗ ਲੀਟਕੋਡ ਹੱਲ ਕਹਿੰਦਾ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਇੱਕ ਗਰਿੱਡ ਦੇ ਆਕਾਰ ਨੂੰ ਦਰਸਾਉਂਦੇ ਹੋਏ ਦੋ ਪੂਰਨ ਅੰਕ ਦਿੱਤੇ ਗਏ ਹਨ. ਦੇ ਆਕਾਰ ਦੀ ਵਰਤੋਂ ਕਰਨਾ ਗਰਿੱਡ, ਗਰਿੱਡ ਦੀ ਲੰਬਾਈ ਅਤੇ ਚੌੜਾਈ. ਸਾਨੂੰ ਗਰਿੱਡ ਦੇ ਉਪਰਲੇ ਖੱਬੇ ਕੋਨੇ ਤੋਂ ਹੇਠਾਂ ਸੱਜੇ ਕੋਨੇ ਤਕ ਵਿਲੱਖਣ ਮਾਰਗਾਂ ਦੀ ਗਿਣਤੀ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਅੰਦੋਲਨ ਦੀ ਦਿਸ਼ਾ ਵਿਚ ਇਕ ਹੋਰ ਰੁਕਾਵਟ ਹੈ, ਕਿਸੇ ਵੀ ਸਮੇਂ, ਕੋਈ ਸਿਰਫ ਹੇਠਾਂ ਜਾਂ ਸਹੀ ਦਿਸ਼ਾ ਵਿਚ ਚਲ ਸਕਦਾ ਹੈ.

ਉਦਾਹਰਨ

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 ਡੀ ਡੀ ਪੀ ਬਣਾਉਂਦੇ ਹਾਂ ਐਰੇ ਅਤੇ ਹਰ ਰਾਜ ਦੇ ਨਤੀਜੇ ਨੂੰ ਸਟੋਰ. ਇਹ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਨੂੰ ਨਾਟਕੀ improveੰਗ ਨਾਲ ਸੁਧਾਰ ਦੇਵੇਗਾ ਕਿਉਂਕਿ ਅਸੀਂ ਉਹੀ ਸਮੱਸਿਆਵਾਂ ਹੱਲ ਨਹੀਂ ਕਰ ਰਹੇ.

ਵਿਲੱਖਣ ਮਾਰਗ ਲੀਟਕੋਡ ਹੱਲ ਲਈ ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਕੋਡ

ਸੀ ++ ਕੋਡ

#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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ * ਐਮ), ਜਿੱਥੇ N, M ਦੀ ਵਰਤੋਂ ਗਰਿੱਡ ਵਿੱਚ ਕਤਾਰਾਂ ਦੀ ਗਿਣਤੀ, ਅਤੇ ਕਾਲਮ ਨੂੰ ਦਰਸਾਉਣ ਲਈ ਕੀਤੀ ਜਾਂਦੀ ਹੈ. ਕਿਉਂਕਿ ਇੱਥੇ ਕੁੱਲ ਐਨ * ਐਮ ਰਾਜ ਹਨ, ਇਸ ਲਈ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਵੀ ਓ (ਐਨ * ਐਮ) ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ * ਐਮ), ਲੋੜੀਂਦੀ ਜਗ੍ਹਾ 2 ਡੀ ਡੀ ਪੀ ਟੇਬਲ ਬਣਾਉਣ ਲਈ ਹੈ. ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ ਡੀ ਪੀ ਪਹੁੰਚ ਲਈ ਬਹੁਪੱਖੀ ਹੈ.