上一题：LeetCode第62题: 不同路径uniquePaths(C语言)

思路：参考62题的思路，递归肯定要直接放弃啦，同样还是要考虑用动态规划来做。与62题不同的是，初始化和计算的时候需要考虑障碍。
1、对于第1行和第1列，一旦遇到障碍，则障碍后续的行列只能是0，因为后续的方格无法抵达；
2、对于其他行列的计算，如果该方格本身就是障碍，则可以直接给该方格赋值0继续；对于非障碍的方格，则要考虑该方格的左邻居和上邻居是否为障碍，是障碍的话不计入结果内即可。
注释：代码中的前两个循环用于初始化首行和首列的

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){

    unsigned int a[obstacleGridSize][*obstacleGridColSize];
    
    /*初始化第一列*/
    for(int i = 0; i < obstacleGridSize; i++){
        if(obstacleGrid[i][0] == 0)
            a[i][0] = 1;
        else{
            for(int j = i; j < obstacleGridSize; j++)
                a[j][0] = 0;
            break;
        }
    }
    
    /*初始化第一行*/
    for(int i = 0; i < *obstacleGridColSize; i++){
        if(obstacleGrid[0][i] == 0)
            a[0][i] = 1;
        else{
            for(int j = i; j < *obstacleGridColSize; j++)
                a[0][j] = 0;
            break;
        }
    }
    
    /*动态规划开始计算*/
    for(int i = 1; i < obstacleGridSize; i++){
        for(int j = 1; j < *obstacleGridColSize; j++){
            a[i][j] = 0; 
            if(obstacleGrid[i][j] == 1)
                continue;
            if(obstacleGrid[i-1][j] == 0)
                a[i][j] += a[i-1][j];
            if(obstacleGrid[i][j-1] == 0)
                a[i][j] += a[i][j-1];
        }
    }
    return a[obstacleGridSize - 1][*obstacleGridColSize - 1];
}

本系列文章，旨在打造LeetCode题目解题方法，帮助和引导同学们开阔学习算法思路，由于个人能力和精力的局限性，也会参考其他网站的代码和思路，如有侵权，请联系本人删除。