Уникално решение на Leetcode  


Ниво на трудност M
Често задавани в Кирпич Амазонка ябълка Bloomberg ByteDance Facebook Goldman Sachs Google Математика Microsoft Оракул Qualtrics Salesforce Snapchat Uber VMware Walmart Labs
алгоритми Array кодиране Динамично програмиране Интервю интерпретация LeetCode LeetCodeSolutions

Проблемът Unique Paths Leetcode Solution гласи, че са ви дадени две цели числа, представляващи размера на мрежа. Използвайки размера на мрежа, дължината и ширината на мрежата. Трябва да намерим броя на уникалните пътеки от горния ляв ъгъл на мрежата до долния десен ъгъл. Има едно друго ограничение за посоката на движение, във всеки момент от времето човек може да се движи само в посока надолу или вдясно.

Пример  

row: 2, column: 2
2

Обяснение: Има само два начина за изпълнение на задачата. Първо или се движите надясно или надолу. Ако сте се движили надясно, можете да се движите само надолу. Ако сте се преместили надолу, тогава можете да се движите само в посока надолу. И така, възможни са само 2 начина.

Уникално решение на Leetcodeщифт

row: 2, column: 3
3

Обяснение: Има 6 начина да стигнете до дестинацията. Помислете, ако сте се преместили надясно, тогава проблемът е сведен до горния пример и имате 2 начина да достигнете до долния десен ъгъл. Ако искате да намалите, тогава имате само един начин да стигнете до долния десен ъгъл. По този начин общият брой начини за достигане до края е 3.

Вижте също
Проверете формирането на масив чрез решение за конкатенация Leetcode

Подход на груба сила за уникално решение с Leetcode  

Проблемът Unique Paths Leetcode Solution може да бъде решен рекурсивно. Точно както направихме във втория пример, където намалихме дадения проблем на 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 ^ макс (m, n)), поради експоненциалната времева сложност поради рекурсивна функция.

Сложност на пространството

O (макс. (M, n), пространството, използвано от стека на компилатора. Това зависи от височината на рекурсивното дърво.

Подход за динамично програмиране  

Подходът, който е обяснен по-горе под рекурсивното решение, може лесно да се запомни. Тъй като рекурсивната функция зависи от две променливи, които са ред и колона. По този начин създаваме 2D DP масив и съхранява резултата от всяко състояние. Това значително ще подобри сложността на времето, тъй като не решаваме едни и същи проблеми.

Вижте също
Минимално време за посещение на всички точки Leetcode Solution

Код за динамично програмиране за решение с уникални пътища 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 таблица. Сложността на пространството е полиномна за DP подход.

1