ವಿಶಿಷ್ಟ ಮಾರ್ಗಗಳು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಆಪಲ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಬೈಟ್ ಡೇನ್ಸ್ ಫೇಸ್ಬುಕ್ ಗೋಲ್ಡ್ಮನ್ ಸ್ಯಾಚ್ಸ್ ಗೂಗಲ್ ಮ್ಯಾಥ್ವರ್ಕ್ಸ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಒರಾಕಲ್ ಗುಣಗಳು ಸೇಲ್ಸ್ಫೋರ್ಸ್ Snapchat ಉಬರ್ ವರೆ ವಾಲ್ಮಾರ್ಟ್ ಲ್ಯಾಬ್ಸ್
ಅರೇ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್

ವಿಶಿಷ್ಟ ಮಾರ್ಗಗಳು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ಗ್ರಿಡ್‌ನ ಗಾತ್ರವನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಎರಡು ಪೂರ್ಣಾಂಕಗಳನ್ನು ನಿಮಗೆ ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಗಾತ್ರವನ್ನು ಬಳಸುವುದು ಗ್ರಿಡ್, ಗ್ರಿಡ್‌ನ ಉದ್ದ ಮತ್ತು ಅಗಲ. ಗ್ರಿಡ್‌ನ ಮೇಲಿನ ಎಡ ಮೂಲೆಯಿಂದ ಕೆಳಗಿನ ಬಲ ಮೂಲೆಯಲ್ಲಿರುವ ಅನನ್ಯ ಮಾರ್ಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕು. ಚಲನೆಯ ದಿಕ್ಕಿನಲ್ಲಿ ಒಂದಕ್ಕೊಂದು ನಿರ್ಬಂಧವಿದೆ, ಯಾವುದೇ ಸಮಯದಲ್ಲಿ, ಒಬ್ಬರು ಕೆಳಕ್ಕೆ ಅಥವಾ ಬಲ ದಿಕ್ಕಿನಲ್ಲಿ ಮಾತ್ರ ಚಲಿಸಬಹುದು.

ಉದಾಹರಣೆ

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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ * ಎಂ), ಅಲ್ಲಿ N, M ಅನ್ನು ಸಾಲುಗಳ ಸಂಖ್ಯೆ ಮತ್ತು ಗ್ರಿಡ್‌ನಲ್ಲಿನ ಕಾಲಮ್‌ಗಳನ್ನು ಪ್ರತಿನಿಧಿಸಲು ಬಳಸಲಾಗುತ್ತದೆ. ಒಟ್ಟು N * M ರಾಜ್ಯಗಳು ಇರುವುದರಿಂದ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಸಹ O (N * M) ಆಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ * ಎಂ), ಅಗತ್ಯವಿರುವ ಸ್ಥಳವು 2 ಡಿ ಡಿಪಿ ಟೇಬಲ್ ರಚನೆಗೆ ಆಗಿದೆ. ಡಿಪಿ ವಿಧಾನಕ್ಕಾಗಿ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯು ಬಹುಪದವಾಗಿದೆ.