Technologieaustausch

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

*62. Verschiedene Wege

Adresse der Leetcode-Frage

Der Wert jeder Zelle wird durch die Zellen darüber und links bestimmt, daher müssen die Zellen oben und ganz links zuerst initialisiert werden. Da die Frage erfordert, dass sie sich nur nach unten und rechts bewegen kann, werden die Zellen oben und ganz links auf 1 initialisiert.

Zeitkomplexität: $Ö(M\ast N)$
Raumkomplexität: $Ö(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. Verschiedene Wege II

Adresse der Leetcode-Frage

Die Idee ähnelt der vorherigen Frage, und Hindernisse werden basierend auf der vorherigen Frage hinzugefügt. Das dp-Array stellt die Anzahl der Wege dar, um die (i, j)-Zelle zu erreichen, und die Hindernisposition im dp-Array ist 0. Wenn ab der Initialisierung der ersten Zeile und Spalte ein Hindernis auf dem Weg erscheint, sind die Zellen hinter dem Hindernis nicht erreichbar und die entsprechenden dp-Array-Werte sind alle 0.

Zeitkomplexität: $Ö(M\ast N)$
Raumkomplexität: $Ö(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