प्रौद्योगिकी साझेदारी

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

*62.विभिन्नमार्गाः

leetcode प्रश्न पता

प्रत्येकस्य कोष्ठकस्य मूल्यं उपरि वामतः च कोष्ठकैः निर्धारितं भवति, अतः उपरि वामयोः कोष्ठकयोः प्रथमं आरम्भः करणीयः । यतः प्रश्ने अपेक्षितं यत् भवान् केवलं अधः दक्षिणतः च गन्तुं शक्नोति, अतः उपरि वामतः च कोष्ठकाः 1 इति आरभन्ते ।

कालजटिलता : १. $ओ(पु\ast न)$
अन्तरिक्षजटिलता : १. $ओ(पु\ast न)$

// 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) कोष्ठकं प्राप्तुं मार्गसङ्ख्यां प्रतिनिधियति, तथा च dp सरणीयां बाधास्थानं 0 भवति । प्रथमपङ्क्तिस्तम्भयोः आरम्भात् आरभ्य यदि मार्गे बाधा दृश्यते तर्हि बाधकस्य पृष्ठतः कोष्ठकाः न प्राप्यन्ते, तत्सम्बद्धानि dp सरणीमूल्यानि सर्वाणि 0 भविष्यन्ति

कालजटिलता : १. $ओ(पु\ast न)$
अन्तरिक्षजटिलता : १. $ओ(पु\ast न)$

// 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