Berbagi teknologi

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

*62.Jalan yang berbeda

alamat pertanyaan kode leet

Nilai setiap sel ditentukan oleh sel di atas dan di sebelah kiri, sehingga sel paling atas dan paling kiri perlu diinisialisasi terlebih dahulu. Karena pertanyaannya mengharuskan hanya bisa bergerak ke bawah dan ke kanan, sel paling atas dan paling kiri diinisialisasi menjadi 1.

kompleksitas waktu: $HAI(M\ast N)$
Kompleksitas ruang: $HAI(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. Jalan yang berbeda II

alamat pertanyaan kode leet

Idenya mirip dengan pertanyaan sebelumnya, dan kendala ditambahkan berdasarkan pertanyaan sebelumnya. Array dp mewakili jumlah jalur untuk mencapai sel (i, j), dan posisi rintangan adalah 0 dalam array dp. Mulai dari inisialisasi baris dan kolom pertama, jika muncul hambatan di jalur, sel di belakang hambatan tidak akan dapat dijangkau, dan nilai larik dp yang sesuai semuanya akan menjadi 0.

kompleksitas waktu: $HAI(M\ast N)$
Kompleksitas ruang: $HAI(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