代码随想录算法训练营day39 ● 62.不同路径 ● 63. 不同路径 II

62.不同路径

//dp数组表示有几种路径可从左边或者上边到达目标点
int uniquePaths(int m, int n){
    int dp[m][n];//到达该点的路径数
    int i,j;
    //每个格子由左边的与上边的得来，从上向下，从左往右遍历
    for(i=0;i<m;i++) dp[i][0] = 1;//最左列只由一步达成
    for(j=0;j<n;j++) dp[0][j] = 1;
    for(i =1;i<m;i++)
    {
        for(j=1;j<n;j++)
        {
            dp[i][j] = dp[i-1][j]+dp[i][j-1];
        }
    }
    return dp[i-1][j-1];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

63. 不同路径 II

//与不同路径的初始化存在差异

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    int m = obstacleGridSize,n = obstacleGridColSize[0];
    int i,j;
    int dp[m][n];
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            dp[i][j]=0;
        }
    }
    
    if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1)
    {
        return 0;
    }
    for(i = 0;i<m;i++) 
    {
        if(obstacleGrid[i][0]==0) dp[i][0]=1; 
        else break;
    }

    for(j = 0;j<n;j++) 
    {
        if(obstacleGrid[0][j]==0) dp[0][j]=1;
        else break;
    }
    for(i = 1;i<m;i++)
    {
        for(j = 1;j<n;j++)
        {
            if(obstacleGrid[i][j]==0)
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
            else continue;
        }
    }

    return dp[m-1][n-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
38
39
40
41