这周两道算法题(四十七)

上周他们弄了一道阿里的面试算法题，没有正确答案，而且题目比较复杂，就不写了，这周两道题是同一种类型的题，就一起做了，难度级别都是'Medium'，使用语言都是'C'。

题目：在一个m*n的格子里，从左上角走到右下角有多少种走法(只能往右和往下走)

思路：这就标准的动态规划题，关于动态规划，可以看看这篇文章,这个题的算法其实就是将第一行和第一列填1，然后左边格子与上边格子的和就是当前格子的数，填到右下角的数就是结果。具体看代码：

int uniquePaths(int m, int n) {
    //定义一个数组
    int res[n];  
    //左边第一个数为1
    res[0] = 1;  
    for(int i=0;i<m;i++)    
        for(int j=1;j<n;j++)  
            //初始化赋值
            if (i == 0) res[j] = 0;
            //左边res[j-1]和上边的数res[j]求和
            res[j] += res[j-1];
    //返回右下角的结果
    return res[n-1]; 
}

接着直接看第二道：

题目：给你一个m*n的格子，格子中有障碍物，我们记为1，遇到障碍物就无法通行了，然后同样的是让你从左上角走到右下角，求有多少种走法。

思路：这个题思路和上面一样，只是遇到障碍物将结果置为0即可，具体看代码：

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize) {
    //如果左上角（起点）或者右下角（重点）有障碍物，直接返回0种走法
    if (obstacleGrid[0][0] || obstacleGrid[obstacleGridRowSize - 1][obstacleGridColSize-1]) return 0;
    //定义容器
    int res[obstacleGridColSize];  
    //左边第一个数为1
    res[0] = 1;  
    
    for(int i = 0;i < obstacleGridRowSize; i++) {    
        for(int j = 0;j < obstacleGridColSize; j++) {
            //初始化赋值
            if (i == 0 && j != 0) res[j] = 0;
            //如果是障碍物，记为0
            if(obstacleGrid[i][j]==1) res[j]=0;   
            //否则如果不是第一列，则加上左边和上边的数
            else if(j) res[j] += res[j-1];  
        }
    }
    return res[obstacleGridColSize-1]; 
}

效率一般，但cpp用这种解法效率就是最好，这种类型的题还有很多种解法，有兴趣的小伙伴可以再尝试用其他的方法解，递归容易超时，就不要用递归了。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!