LeetCode 63. Unique Paths II (动归)

比眉伴天荒 2024-04-17 23:26 92阅读 0赞

题目信息：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1][]

这道题是上一道题的亲兄弟，上道题用数学公式过了，这道题升了个级，加了个障碍物，想了想还是别绕弯了，老老实实动归吧。

思路在注释中。

class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
            //障碍物的格子就不通嘛，直接设置0条路径
            //你看题目多好，连dp的二维状态数组都给了，它白给我们白拿
            //dp[0][0] = 1
            //dp[1][0] = d[i-1][0]
            //dp[0][1] = d[i][j-1]
            //上面给了几个示例我们可以推出我们的状态转移公式：
            //dp[i][j] = dp[i-1][j] + dp[i][j-1]  if(obstacleGrid[i][j]!=1)
            //dp[i][j] = 0  if(dp[i][j]==1) 有障碍物很明显此路不通
            int n = obstacleGrid.size();
            int m = obstacleGrid[0].size();
            long dp[n+5][m+5];
            memset(dp, 0, sizeof(dp));
            //记录是否初始化
            int initFlag = 0;
            //老规矩从1开始，外围做一圈padding
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    if(obstacleGrid[i-1][j-1] == 0) dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    //初始化起始点
                    //放在这里不会被上面那行代码覆盖掉
                    if (initFlag == 0){
                        dp[1][1] = 1;
                        initFlag = 1;
                    }
                    //放在这里可以判断只有一个障碍物的情况,不会被上面那行代码覆盖掉
                    if(obstacleGrid[i-1][j-1] == 1) dp[i][j] = 0;
                }
            }
            return dp[n][m];
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2][]

这道题dp数组卡了个long，卡了个\[\[1\]\]，兄弟萌小心。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/d321da51a448459dae559c68c38fc1b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/57373b0d0fd44b30ab6afa923370658f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/34e73c82ede34cc2b3ce6a9faa160078.png