63 Unique Paths II

题目

63 Unique Paths II

题解

在《啊哈！灵机一动》的问题“复杂的路”(Aha! Insight - perplexing path)中，对类似的问题有非常好的阐述。

因为机器人只能向右或者向下走，所以对于方格\((row, column)\)，若它没有障碍物，则它的路径数等于左邻居和上邻居之和，即\(Path(row, column) = Path(row, column-1) + Path(row-1, column)\)；若有障碍物，则该方格不能被通过，其路径数为0。

基于上述观察，我们只要把起点的路径数设为1，界外方格的路径数设为0，从起点开始动态规划即可求出答案。动态规划时，从起点出发分别沿着右方向和下方向更新路径数，然后将起点往右下方移动一格。重复这个过程，直到抵达终点为止。

思考：如果没有障碍物的存在，那么各个方格的路径数呈现为帕斯卡三角

代码

class Solution
{
  public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        int row = 1;
        int column = 1;

        int row_num = obstacleGrid.size();
        int column_num = obstacleGrid[0].size();

        int **counts = new int *[row_num + 1];
        for (int i = 0; i < row_num + 1; i++)
        {
            counts[i] = new int[column_num + 1];
        }

        for (int i = 0; i <= row_num; i++)
        {
            for (int j = 0; j <= column_num; j++)
            {
                counts[i][j] = 0;
            }
        }

        counts[0][1] = 1;

        while (row <= row_num && column <= column_num)
        {
            for (int i = row; i <= row_num; i++)
            {
                if (obstacleGrid[i - 1][column - 1] != 1)
                {
                    counts[i][column] = counts[i - 1][column] + counts[i][column - 1];
                }
                else
                {
                    counts[i][column] = 0;
                }
            }
            column++;

            for (int j = column; j <= column_num; j++)
            {
                if (obstacleGrid[row - 1][j - 1] != 1)
                {
                    counts[row][j] = counts[row - 1][j] + counts[row][j - 1];
                }
                else
                {
                    counts[row][j] = 0;
                }
            }
            row++;
        }

        return counts[row_num][column_num];
    }
};