Unique Paths I & II
in LeetCode with 0 comment

Unique Paths I & II

in LeetCode with 0 comment
Unique Paths 入门级动态规划,我一开始用递归做了一下,直接超时了//// 2333

二维数组动态规划

这里给机器人增加了障碍物,需要在递推式resi=resi-1+resi之前增加一个判断,

如果则resi=0,则resi = 0 (当然res初始化全部成0,所以可以直接跳过)

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int i, j, m = obstacleGrid.size(), n = obstacleGrid[0].size();
                // 默认所有地方都是堵着的
        vector<vector<int> > dp(m, vector<int>(n, 0));
        // 两头堵住了
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
            return 0;
        }
                //初始化动态规划矩阵dp
        for (i = 0; i < m&&obstacleGrid[i][0] == 0; i++) {
                dp[i][0] = 1;
        }
        for (j = 0; j < n&&obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;
        }
        for (i = 1; i < m; i++) {
            for (j = 1; j < n; j++) {
                if(obstacleGrid[i][j]==0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];

    }
};

一维数组

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        vector<int> dp(obstacleGrid[0].size(), 0);

        for (int i = 0; i < obstacleGrid[0].size() && obstacleGrid[0][i] == 0; ++i)
        {
            dp[i] = 1;
        }

        for (int i = 1; i < obstacleGrid.size(); ++i)
        {
            if (obstacleGrid[i][0] == 1)
            {
                dp[0] = 0;
            }

            for (int j = 1; j < obstacleGrid[i].size(); ++j)
            {
                dp[j] = obstacleGrid[i][j] == 0 ? dp[j] + dp[j - 1] : 0;
            }
        }

        return dp.back();
    }
};

递归算法

本方法会超时

class Solution {
public:
    // 目前在第i行,第j列
    int uniquePaths(vector<vector<int>>& obstacleGrid, int i, int j) {
        if (i == obstacleGrid.size() - 1 && j == obstacleGrid[0].size() - 1 && obstacleGrid[i][j] == 0)
            return 1;
        if (i + 1 < obstacleGrid.size() && j + 1 < obstacleGrid[0].size() && obstacleGrid[i + 1][j] == 0 && obstacleGrid[i][j + 1] == 0)
            return uniquePaths(obstacleGrid, i + 1, j) + uniquePaths(obstacleGrid, i, j + 1);
        if (i + 1 < obstacleGrid.size() && obstacleGrid[i + 1][j] == 0)
            return uniquePaths(obstacleGrid, i + 1, j);
        if (j + 1 < obstacleGrid[0].size() && obstacleGrid[i][j + 1] == 0)
            return uniquePaths(obstacleGrid, i, j + 1);
        return 0;
    }
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid[0][0] == 1)
            return 0;
        return uniquePaths(obstacleGrid, 0, 0);
    }
};

小结

看起来递归是最挫的方法,但是最好理解。

二维数组的方法其实也挺好理解的,一维数组感觉有点费解,不太显然的感觉。

Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号