Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

*62. Διαφορετικά μονοπάτια

διεύθυνση ερώτησης leetcode

Η τιμή κάθε κελιού καθορίζεται από τα κελιά πάνω και στα αριστερά, επομένως το επάνω και το αριστερό κελί πρέπει πρώτα να αρχικοποιηθούν. Επειδή η ερώτηση απαιτεί να μπορείτε να μετακινηθείτε μόνο προς τα κάτω και προς τα δεξιά, το επάνω και το αριστερό κελί αρχικοποιούνται σε 1.

χρονική πολυπλοκότητα: ${\rm O}({\rm M}\ast n)$
Πολυπλοκότητα χώρου: ${\rm O}({\rm M}\ast n)$

// c++
class Solution {
public:
    
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector(n,0));
        for(int i=0; i<m; i++) dp[i][0] = 1;
        for(int j=0; j<n; j++) dp[0][j] = 1;
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

63. Διαφορετικά μονοπάτια II

διεύθυνση ερώτησης leetcode

Η ιδέα είναι παρόμοια με την προηγούμενη ερώτηση και προστίθενται εμπόδια με βάση την προηγούμενη ερώτηση. Ο πίνακας dp αντιπροσωπεύει τον αριθμό των μονοπατιών για να φτάσει στο κελί (i, j) και η θέση του εμποδίου είναι 0 στον πίνακα dp. Ξεκινώντας από την προετοιμασία της πρώτης γραμμής και στήλης, εάν εμφανιστεί ένα εμπόδιο στη διαδρομή, τα κελιά πίσω από το εμπόδιο δεν θα είναι προσβάσιμα και οι αντίστοιχες τιμές του πίνακα dp θα είναι όλες 0.

χρονική πολυπλοκότητα: ${\rm O}({\rm M}\ast n)$
Πολυπλοκότητα χώρου: ${\rm O}({\rm M}\ast n)$

// c++
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        vector<vector<int>> dp(obstacleGrid.size(), vector(obstacleGrid[0].size(), 0));
        // 标志单元格是否可到达
        bool flag = true;
        // 初始化第一行
        for(int i=0; i<obstacleGrid.size(); i++){
            if(obstacleGrid[i][0] == 1) {
            	// 可以直接break
            	flag = false;
            }
            if(flag) dp[i][0] = 1;
            else dp[i][0] = 0;
        }
        // 标志单元格是否可到达
        flag = true;
        // 初始化第一列
        for(int j=0; j<obstacleGrid[0].size(); j++){
            if(obstacleGrid[0][j] == 1) {
            	// 可以直接break
            	flag = false;
            }
            if(flag) dp[0][j] = 1;
            else dp[0][j] = 0;
        }
        // 计算dp数组
        for(int i=1; i<obstacleGrid.size(); i++){
            for(int j=1; j<obstacleGrid[0].size(); j++){
                if(obstacleGrid[i][j]==1) continue;
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[obstacleGrid.size()-1][obstacleGrid[0].size()-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37