منفرد رستو ليٽ ڪوڊ حل


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ ايڊوب Amazon ايپل Bloomberg ByteDance ڪريو Goldman سيچ گوگل رياضيات Microsoft جي Oracle قوتون Salesforce، Snapchat سليمان وساڻ VMware والارٽ ليبز
ڪيريو متحرڪ پروگرامنگ

مسئلو منفرد رستا ليٽ ڪوڊ حل ٻڌائي ٿو ته توهان کي گرڊ جي سائيز جي نمائندگي ڪرڻ لاءِ ٻه انٽيگرم ڏنا ويا آهن. جِي ماپ جو استعمال ڪرڻ گرڊ، گرڊ جي ڊيگهه ، ۽ چوٿون. اسان کي گرڊ جي مٿين کاٻي ڪنڊ کان هيٺيون سا cornerي ڪنڊ تائين منفرد رستن جو تعداد ڳولڻ جي ضرورت آهي. حرڪت جي طرف هڪ ٻي رڪاوٽ آهي ، وقت جي ڪنهن به وقت ، رڳو هڪ هيٺ يا صحيح طرف وڃي سگھجي ٿو.

مثال

row: 2, column: 2
2

وضاحت: ڪم کي مڪمل ڪرڻ جا ٻه طريقا ممڪن آهن. پهرين يا ته توهان سا theي يا هيٺ وڃو. جيڪڏهن توهان صحيح منتقل ڪئي ته توهان صرف هيٺ ٿي سگهو ٿا. جيڪڏھن توھان ھيٺ ھليو ھو ، تڏھن توھان صرف ھيٺئين طرف وڃي سگھوٿا. تنهن ڪري ، صرف 2 طريقا ممڪن آهن.

منفرد رستو ليٽ ڪوڊ حل

row: 2, column: 3
3

وضاحت: منزل تي پهچڻ جا 6 طريقا آهن. غور ڪريو جيڪڏھن توھين حق ڏانھن ھليو ويو ، ته پوءِ مسئلو مٿئين مثال ڏانھن گھٽجي ويو آھي ۽ توھان وٽ 2 صحيح طريقي سان پھريائين ته ھيٺ صحيح سا cornerي طرف جيڪڏهن توهان هيٺ هجو ها ، ته توهان وٽ هيٺيون سا cornerي ڪنڊ تائين پهچڻ جو واحد رستو آهي. اھڙيءَ طرح ، آخر تائين پھچڻ جا طريقا 3 آھن.

منفرد رستا ليٽ ڪوڊ حل لاءِ بروٽ فورس نقطه نظر

مسئلو منفرد رستن جو ليٽ ڪوڊ حل ٻيهر تئين سان حل ٿي سگھي ٿو. جيئن ته اسان ٻئي مثال ۾ ڪيو ، جئين اسان ڏنل مسئلي کي 2 ذيلي تقاضا ۾ گهٽايو. ساڳي شيءَ اسان ڇا ڪنداسين انهي حل ۾. هڪ دفعو ، اسان سا moveي طرف منتقل ڪريون ٿا ، پوءِ اهو مسئلو سبجيم ڏانهن گهٽجي ويو آهي (قطار ، ڪالمن -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 ^ وڌ (م ، ن)) ، recursive function جي معروضي وقت جي پيچيدگي جي ڪري.

خلائي پيچيدگي

اي (وڌ (م ، ن) ، compiler اسٽيڪ طرفان استعمال ڪيل جڳهه. اهو انحصار ڪندڙ وڻ جي قد تي منحصر آهي.

متحرڪ پروگرامنگ جو طريقيڪار

نقطه نظر حل جي هيٺ ڏنل طريقي سان جيڪا وضاحت ڪئي وئي آهي اها آسانيءَ سان ياد ڪري سگهجي ٿي. جئين بحالي وارو فنڪشن ٻن متغير تي منحصر آهي جيڪي قطار ، ۽ ڪالمن آهن. اهڙي طرح اسان 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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين * ايم) ، جتي اين ، ايم گرڊ ۾ قطارن ۽ ڪالمن جي تعداد جي نمائندگي لاءِ استعمال ڪيا ويندا آهن. جيئن ته اين اين ايم اي رياستون آهن ، وقت جي پيچيدگي پڻ آهي اي (اين * ايم).

خلائي پيچيدگي

اي (اين * ايم) ، گهربل جڳھ 2D DP ٽيبل جي ٺاھڻ لاءِ آھي. خلائي پيچيدگي ڊي پي جي اچڻ واري پالشين لاءِ آهي.