leetcode63同路径 II

柔光的暖阳◎ 2022-09-05 00:10 141阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]  
思路

1.  动态规划，在没有障碍物的时候`dp[i][j] = dp[i-1][j] + dp[i][j-1]`，当一旦有障碍物时`dp[i][j] = 0`也就是此路不通，任何需要借助这个位置的路径都不可以在此位置上获得该点的路径加成。
2.  在边界位置`dp[i][j] = d[i-1][j];dp[i][j] = dp[i][j-1]`上一个节点有路那么就有路而且是一条，如果没有就是没有了
3.  初始位置不在一定是1，如果初始位置是障碍物的位置，那么`dp[0][0]=0 or dp[0][0] = 1;`

代码

#include<stdio.h>
    #include<string.h>
    int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){ 
        int i,j;
        int dp[obstacleGridSize][*obstacleGridColSize];
        memset(dp,0,sizeof(dp));
        if(*((int*)obstacleGrid)==1)
            dp[0][0] = 0;
        else dp[0][0] = 1;
        for(i=0;i<obstacleGridSize;i++){ 
            for(j=0;j<*obstacleGridColSize;j++){ 
                if(*((int*)obstacleGrid+i*(obstacleGridColSize)+j)==1)
                        dp[i][j] = 0;
                else { 
                    if(i>0&&j>0)
                        dp[i][j]=dp[i-1][j]+dp[i][j-1];
                    else if(i==0&&j==0)
                    	dp[i][j] = 1;
                    else if(i==0)
                        dp[i][j] = dp[i][j-1];
                    else if(j==0)
                        dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[obstacleGridSize-1][(*obstacleGridColSize)-1];
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20220829/cd7f89ed319b4e9a87084b2ac7a1d890.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20220829/8531cc9ab28543cdb6980d0fba085514.png