Өвөрмөц замууд Leetcode шийдэл


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Амазоны Apple-ийн Bloomberg БайтДанс Facebook-ийн Goldman Sachs Google-ийн Математикийн ажил Microsoft- Oracle-ийн Qualtrics Борлуулалтын хүч Snapchat Uber VMware Walmart лабораторууд
Array Динамик програмчлал

Unique Paths Leetcode Solution-ийн асуудалд танд торны хэмжээг илэрхийлсэн хоёр бүхэл тоо өгөгдсөн гэж мэдэгджээ. -Ийн хэмжээг ашиглан сүлжээ, сүлжээний урт ба өргөн. Сүлжээний зүүн дээд булангаас баруун доод булан хүртэлх өвөрмөц замын тоог олох хэрэгтэй. Хөдөлгөөний чиглэлд өөр нэг хязгаарлалт байдаг тул цаг хугацааны аль ч үед хүн зөвхөн доош эсвэл баруун тийш хөдөлж чаддаг.

Жишээ нь

row: 2, column: 2
2

Тайлбар: Даалгаврыг гүйцэтгэхэд зөвхөн хоёр арга л боломжтой. Эхлээд та баруун тийш эсвэл доошоо хөдөлнө. Хэрэв та зөв хөдөлсөн бол зөвхөн доошоо л хөдөлж болно. Хэрэв та доошоо хөдөлсөн бол зөвхөн доошоо чиглэлд л хөдөлж болно. Тиймээс зөвхөн 2 арга л боломжтой.

Өвөрмөц замууд Leetcode шийдэл

row: 2, column: 3
3

Тайлбар: Очих газраа хүрэх 6 арга байдаг. Хэрэв та баруун тийш шилжсэн бол асуудлыг дээрх жишээ болгон бууруулж, баруун доод буланд хүрэх 2 арга байна гэж үзээрэй. Хэрэв та доошоо буухыг хүсч байвал баруун доод буланд хүрэх цорын ганц арга байна. Тиймээс төгсгөл хүрэх нийт арга замуудын тоо 3 байна.

Өвөрмөц замнуудын Leetcode шийдлийг ашиглах хүчирхийллийн арга

Өвөрмөц замын Leetcode шийдлийн асуудлыг рекурсив байдлаар шийдвэрлэх боломжтой. Бид хоёрдахь жишээнд өгөгдсөн бодлогыг 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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (2 ^ max (m, n)), рекурсив функцтэй холбоотой экспоненциаль цаг хугацааны нарийн төвөгтэй байдгаас.

Сансрын нарийн төвөгтэй байдал

O (хамгийн их (m, n), хөрвүүлэгч стекийн ашигласан зай. Энэ нь рекурсив модны өндрөөс хамаарна.

Програмчлалын динамик хандлага

Рекурсив шийдлийн дагуу дээр тайлбарласан аргыг амархан цээжилж болно. Рекурсив функц нь мөр, баганатай хоёр хувьсагчаас хамаардаг тул. Тиймээс бид 2D АН үүсгэдэг массив муж бүрийн үр дүнг хадгалах. Энэ нь бид ижил асуудлуудыг шийдэж чадахгүй байгаа тул цаг хугацааны нарийн төвөгтэй байдлыг эрс сайжруулах болно.

Өвөрмөц замын Leetcode шийдлийн динамик програмчлалын код

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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N * M), энд N, M нь эгнээний мөр, баганын тоог илэрхийлэхэд хэрэглэгддэг. Нийт N * M төлөв байдаг тул цаг хугацааны нарийн төвөгтэй байдал нь O (N * M) болно.

Сансрын нарийн төвөгтэй байдал

O (N * M), шаардлагатай зай нь 2D DP хүснэгт үүсгэхэд зориулагдсан болно. Сансрын нарийн төвөгтэй байдал нь АН-ын хандлагын хувьд олон гишүүнт зүйл юм.