יינציק פּאַטס לעעטקאָדע סאַלושאַן  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַדאָובי אַמאַזאָן עפּל בלומבערג ביטעדאַנסע facebook גאָלדמאַן סאַקס גוגל מאַטהוואָרקס מייקראָסאָפֿט אָראַקל Qualtrics סאַלעספאָרסע Snapchat ובער וומוואַרע וואַלמאַרט לאַבס
אַלגערידאַמז מענגע קאָדירונג דינאַמיש פּראָגראַממינג אינטערוויו interviewprep LeetCode LeetCodeSolutions

דער פּראָבלעם יינציק פּאַטס לעעטקאָדע סאַלושאַן שטאַטן אַז איר האָט צוויי ינטאַדזשערז וואָס רעפּראַזענץ די גרייס פון אַ גריד. ניצן די גרייס פון דעם גרידדי לענג און די ברייט פון די גריד. מיר דאַרפֿן צו געפֿינען די נומער פון יינציק פּאַטס פֿון די שפּיץ לינקס ווינקל פון די גריד צו די רעכט רעכט ווינקל. די באַוועגונג ריכטונג איז איינער פון די אנדערע, אין קיין צייט קען מען מאַך נאָר אין אַראָפּ אָדער רעכט ריכטונג.

בייַשפּיל  

row: 2, column: 2
2

דערקלערונג: עס זענען בלויז צוויי וועגן צו דורכפירן די אַרבעט. ערשטער אָדער איר מאַך צו די רעכט אָדער אַראָפּ. אויב איר אריבערגעפארן רעכט איר קענען מאַך נאָר אַראָפּ. אויב איר האָט אריבערגעפארן אַראָפּ, איר קענט בלויז מאַך אין די אַראָפּ ריכטונג. אַזוי, בלויז 2 וועגן זענען מעגלעך.

יינציק פּאַטס לעעטקאָדע סאַלושאַן

row: 2, column: 3
3

דערקלערונג: עס זענען 6 וועגן צו דערגרייכן די דעסטיניישאַן. באַטראַכטן אויב איר אריבערגעפארן צו די רעכט, די פּראָבלעם איז רידוסט צו די אויבן ביישפּיל און איר האָבן 2 וועגן צו דערגרייכן די רעכט רעכט ווינקל. אויב איר וואָלט האָבן אַראָפּ, איר האָבן בלויז איין וועג צו דערגרייכן די רעכט רעכט ווינקל. די גאַנץ נומער פון וועגן צו דערגרייכן דעם סוף איז 3.

ברוט פאָרס אַפּפּראָאַטש פֿאַר יינציק פּאַטס לעעטקאָדע סאַלושאַן  

דער פּראָבלעם יינציק פּאַטס לעעטקאָדע סאַלושאַן קענען זיין סאַלווד רעקורסיוועלי. פּונקט ווי מיר האָבן געטאן אין די רגע בייַשפּיל, ווו מיר רידוסט די געגעבן פּראָבלעם אין 2 סאַב-פּראָבלעמס. די זעלבע זאַך איז וואָס מיר וועלן טאָן אין דעם לייזונג. אַמאָל מיר מאַך צו די רעכט, דער פּראָבלעם איז רידוסט צו סאַב-פּראָבלעם (רודערן, זייַל -1). אויב מיר האָבן אריבערגעפארן אין די אַראָפּ ריכטונג, די פּראָבלעם איז רידוסט אין (רודערן -1, זייַל). מיר קענען לייכט קאָד דעם רעקורסיווע לייזונג. אָבער דאָס וועט יקסיד די צייט שיעור ווייַל די לייזונג איז גאָר באַטלאָניש.

זע אויך
קאָנטראָליר די פאָרמירונג פאָרמירונג דורך קאָנקאַטענאַטיאָן לעעטקאָדע סאַלושאַן

קאָד פֿאַר ברוט פאָרס צוגאַנג

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

Java קאוד

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 ^ מאַקס (m, n)), ווייַל פון די עקספּאָונענשאַל צייט קאַמפּלעקסיטי רעכט צו רעקורסיווע פונקציע.

ספעיס קאַמפּלעקסיטי

אָ (מאַקס (m, n), דער פּלאַץ געניצט דורך די קאַמפּיילער אָנלייגן. דעם דעפּענדס אויף די הייך פון די רעקורסיווע בוים.

דינאַמיש פּראָגראַממינג אַפּפּראָאַטש  

דער צוגאַנג וואָס איז געווען דערקלערט אויבן אונטער די רעקורסיווע לייזונג קענען זיין לייכט מעמערייזד. זינט די רעקורסיווע פונקציע איז אָפענגיק אויף צוויי וועריאַבאַלז וואָס זענען רודערן און זייַל. אזוי מיר מאַכן 2 ד דפּ מענגע און קראָם די רעזולטאַט פון יעדער שטאַט. דאָס וועט דראַמאַטיקאַלי פֿאַרבעסערן די צייט קאַמפּלעקסיטי ווייַל מיר זענען נישט סאַלווינג די זעלבע פּראָבלעמס.

דינאַמיש פּראָגראַממינג קאָד פֿאַר יינציק פּאַטס לעעטקאָדע סאַלושאַן

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

Java קאוד

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 זענען געניצט צו רעפּראַזענץ די נומער פון ראָוז און שפאלטן אין די גריד. זינט עס זענען גאַנץ N * M שטאַטן, די צייט קאַמפּלעקסיטי איז אויך O (N * M).

זע אויך
מינימום צייט צו באַזוכן אַלע פּאָינץ לעעטקאָדע סאַלושאַן

ספעיס קאַמפּלעקסיטי

אָ (N * M), די פארלאנגט פּלאַץ איז צו שאַפֿן אַ 2 ד דפּ טיש. די אָרט קאַמפּלעקסיטי איז פּאַלינאָומיאַל פֿאַר דפּ צוגאַנג.