Единствени решенија за Leetcode за патеки


Ниво на тешкотија Медиум
Често прашувано во Adobe Амазон Јаболко Блумберг ByteDance Facebook Голдман Сакс Google Математички дела Мајкрософт Oracle Qualtrics Salesforce Snapchat Uber VMware Лаборатории Walmart
Низа Динамичко програмирање

Проблемот Единствени патеки Решение за лет код наведува дека ви се дадени два интеграла што ја претставуваат големината на мрежата. Користење на големината на мрежа, должината и ширината на решетката. Треба да го најдеме бројот на уникатни патеки од горниот лев агол на решетката до долниот десен агол. Постои една друга ограничување за правецот на движење, во кое било време може да се движи само во или надолу или во вистинска насока.

пример

row: 2, column: 2
2

Објаснување: Постојат само два можни начина да се заврши задачата. Прво или се движите надесно или надолу. Ако се движевте десно, можете да се движите само надолу. Ако се движевте надолу, тогаш можете да се движите само во насока надолу. Значи, можни се само 2 начини.

Единствени решенија за Leetcode за патеки

row: 2, column: 3
3

Објаснување: Постојат 6 начини да стигнете до дестинацијата. Размислете дали сте се преселиле надесно, тогаш проблемот е намален на горенаведениот пример и имате два начина да стигнете до долниот десен агол. Ако би се спуштиле надолу, тогаш имате само еден начин да стигнете до долниот десен агол. Така, вкупниот број на начини да се постигне крајот е 2.

Пристап на брутална сила за единствени решенија за леткод на патеки

Проблемот Единствени патеки Решение за лет код може да се реши рекурзивно. Исто како што сторивме во вториот пример, каде што дадениот проблем го сведовме на 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 ^ макс (м, н)), поради експоненцијалната временска сложеност поради рекурзивната функција.

Комплексноста на просторот

O (максимум (m, n), просторот што го користи магацинот на компајлерот. Ова зависи од висината на рекурзивното дрво.

Пристап на динамичко програмирање

Пристапот што е објаснет погоре под рекурзивно решение може лесно да се запомни. Бидејќи рекурзивната функција зависи од две променливи кои се ред и колона. Така создаваме 2D ДП низа и складирајте го резултатот од секоја држава. Ова драматично ќе ја подобри сложеноста на времето затоа што не ги решаваме истите проблеми.

Динамички код за програмирање за единствени решенија за леткод на патеки

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 состојби, временската сложеност е исто така O (N * M).

Комплексноста на просторот

О (Н * М), просторот што е потребен е за создавање на табела со 2Д ДП. Комплексноста на просторот е полином за пристапот на ДП.