当前位置：首页 > article >正文

代码随想录第三十四天

article 2024/11/19 9:54:49

62.不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

思路：

第一种方法把整个看成一个二叉树，然后我们把能够满足条件的方法看成叶子节点，当我们能到达叶子节点时我们就说有一种方法能够满足，然后加起来就行了，因为用了递归，所以超时了。后面我们用递归的方法，把第一行和第一列的方法设置为一种，然后我们只能向下移动或者向右移动，所以我们得到dp[i][j]=dp[i-1][j]+dp[i][j-1]这个方程，最后我们通过寻找m-1，n-1的次数得到答案。

解答：

第一种方法(深度优先)

int travelback(int startm,int startn,int m,int n)
{
    if(startm > m || startn > n)return 0;
    if(startm == m && startn == n)return 1;
    return travelback(startm,startn,m-1,n)+travelback(startm,startn,m,n-1);
}
int uniquePaths(int m, int n) {    
    return travelback(1,1,m,n);
}

第二种方法(递归)

int uniquePaths(int m, int n) {
    int dp[m][n];
    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];
}

63.不同路径||

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含任何有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 10^9。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

思路：

这道题跟上一道题目很像，但是这道题多了一些条件，我们要注意哪些地方有障碍，如果有障碍，那么我们就不能走这条路。所以我们定义一个二维数组 dp[i][j]，表示从起点 (0, 0) 到网格位置 (i, j) 的路径总数。初始时，若起点或终点为障碍物，则无法到达，直接返回 0。首先初始化第一行和第一列的路径数，如果某一位置存在障碍物，则该位置及后续路径数均为 0，表示不可达。随后从网格的 (1, 1) 开始迭代计算，对于每个非障碍物位置 (i, j)，路径数为从上方 (i-1, j) 和左方 (i, j-1) 到达该位置路径数之和，即 dp[i][j] = dp[i-1][j] + dp[i][j-1]；若当前格子是障碍物，则 dp[i][j] = 0。最终，右下角 dp[m-1][n-1] 的值即为从起点到终点的唯一路径数。

解答：

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