【Unique Paths II】cpp

题目：

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[

  [0,0,0],

  [0,1,0],

  [0,0,0]

]

The total number of unique paths is 2.

Note: m and n will be at most 100.

代码：

class Solution {

public:

        int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid)

        {

            const int m = obstacleGrid.size();

            const int n = obstacleGrid[].size();

            vector<vector<int> > cache(m+,vector<int>(n+,));

            return Solution::dfs(m, n, cache, obstacleGrid);

        }

        static int dfs( int i, int j, vector<vector<int> >& cache, vector<vector<int> >& obstacleGrid )

        {

            if ( i< || j< || obstacleGrid[i-][j-]== ) return ;

            if ( i== && j== ) return ;

            return Solution::getDFS(i-, j, obstacleGrid, cache) + Solution::getDFS(i, j-, obstacleGrid, cache);

        }

        static int getDFS(int i, int j, vector<vector<int> >& obstacleGrid, vector<vector<int> >& cache)

        {

            if ( cache[i][j]> ){

                return cache[i][j];

            }

            else{

                return cache[i][j] = Solution::dfs(i, j, cache, obstacleGrid);

            }

        }

};

tips：

上述的代码采用了深搜+缓存（“备忘录”）法。照比Unique Paths多了一个判断条件，如果obstacleGrid上该位置为1则直接返回0。

有个细节上的技巧：

obstacleGrid是题目给出的定义，下标[m-1][n-1]

cache是自定义的缓存数组，下标[m][n]

同样的位置，cache的坐标比obstacleGrid大1；因此，只要深搜过程中保证了cache的坐标在合理范围内，无论是横坐标-1还是纵坐标-1，映射到cache的坐标中总不会越界。

上述代码的效率并不高，但是比较容易处理各种case。再尝试动态规划的解法。

==========================================

在Unique Paths的基础上，用动规又把Unqiue Paths II写了一遍。

class Solution {

public:

        int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid)

        {

            const int m = obstacleGrid.size();

            const int n = obstacleGrid[].size();

            vector<int> dp(n, );

            if ( obstacleGrid[][]== ) return ;

            dp[] = ;

            for ( size_t i = ; i < m; ++i )

            {

                dp[] = obstacleGrid[i][]== ?  : dp[];

                for ( size_t j =; j < n; ++j )

                {

                    dp[j] = obstacleGrid[i][j]== ?  : dp[j-] + dp[j];

                }

            }

            return dp[n-];

        }

};

tips：

沿用了滚动数组的技巧，额外空间缩减为O(n)，代码的效率也提升了。

==========================================

第二次过这道题，用dp过的。

class Solution {

public:

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

            if (obstacleGrid.empty()) return ;

            const int m = obstacleGrid.size();

            const int n = obstacleGrid[].size();

            int dp[m][n];

            fill_n(&dp[][], m*n, );

            for ( int i=; i<n; ++i )

            {

                if ( obstacleGrid[][i]== )

                {

                    dp[][i]=;

                }

                else

                {

                    break;

                }

            }

            for ( int i=; i<m; ++i )

            {

                if ( obstacleGrid[i][]== )

                {

                    dp[i][]=;

                }

                else

                {

                    break;

                }

            }

            for ( int i=; i<m; ++i )

            {

                for ( int j=; j<n; ++j )

                {

                    if ( obstacleGrid[i][j]== )

                    {

                        dp[i][j] = dp[i-][j] + dp[i][j-];

                    }

                }

            }

            return dp[m-][n-];

    }

};

巴特西

【Unique Paths II】cpp

最新文章

热门文章