力扣题解63-不同路径-ii

题目

63.不同路径-ii
本题采用动态规划解法。

分析

此题在未进行空间优化使用二维数组的方案时，可以很好地解决边界问题。
若需要优化空间，处理边界问题为要务。
此处把输入的数组的行用 r(row)表示，列用 c(column)表示
dp[r][c]表示到达对应位置拥有的方法数，此时在网格位置用 pos 标记
则有如下情况：

pos 处有障碍物

dp[r][c] = 0

pos 处在上边界（r == 0）

# dp[r][c] 在上边界第一个障碍物处分界，障碍物左边为 1，右边为 0，单独进行边界处理
dp[r][c] = 0 || 1

pos 处在左边界（c == 0）

dp[r][c] = dp[r - 1][c]

其他普通情况

1: pos只左边有障碍物 dp[r][c] = dp[r][c - 1]
2: pos只上边有障碍物 dp[r][c] = dp[r - 1][c]
3: pos左边上边都有障碍物 dp[r][c] = 0
4: pos都无障碍物 dp[r][c] = dp[r][c - 1] + dp[r - 1][c]

上述分析可以得到一个初步的代码版本

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:

        columnLen = len(obstacleGrid[0])
        rowLen = len(obstacleGrid)
        note = [0] * columnLen

        # 处理初始上边界并用记事本note保存
        for i,v in enumerate(obstacleGrid[0]):
            if v == 1:
                break
            note[i] = 1

        if rowLen == 1:
            return note[-1]

        ret = 0
        for r in range(1, rowLen):
            for c in range(columnLen):

                # 当前位置为障碍物
                if obstacleGrid[r][c] == 1:
                    ret = 0
                    note[c] = 0
                    continue

                # 当前位置位于左边界
                if c == 0:
                    ret = note[c]
                    continue

                # 普通情况
                if obstacleGrid[r - 1][c] == 1:
                    if obstacleGrid[r][c - 1] == 1:
                        ret = 0
                        note[c] = 0
                    else:
                        note[c] = ret
                else:
                    if obstacleGrid[r][c - 1] == 1:
                        ret = note[c]
                    else:
                        ret = ret + note[c]
                        note[c] = ret

        return ret

普通情况可进行合并

普通情况合并
1: pos只左边有障碍物 dp[r - 1][c] = 0，  dp[r][c] = dp[r][c - 1] + dp[r - 1][c]
2: pos只上边有障碍物 dp[r][c - 1] = 0， dp[r][c] = dp[r][c - 1] + dp[r - 1][c]
3: pos左边上边都有障碍物 dp[r - 1][c] = 0， dp[r][c - 1] = 0， dp[r][c] = dp[r][c - 1] + dp[r - 1][c]
4: pos都无障碍物 dp[r][c] = dp[r][c - 1] + dp[r - 1][c]

即普通情况下

dp[r][c] = dp[r][c - 1] + dp[r - 1][c]

则解法如下

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:

        columnLen = len(obstacleGrid[0])
        rowLen = len(obstacleGrid)
        note = [0] * columnLen
        ret = 0

        # 处理初始上边界并用记事本note保存(滚动数组)
        for i,v in enumerate(obstacleGrid[0]):
            if v == 1:
                break
            note[i] = 1

        if rowLen == 1:
            return note[-1]

        for r in range(1, rowLen):
            for c in range(columnLen):

                # 当前位置为障碍物
                if obstacleGrid[r][c] == 1:
                    ret = 0
                    note[c] = 0
                    continue
                # 当前位置位于左边界
                if c == 0:
                    ret = note[c]
                    continue

                # 普通情况
                ret = ret + note[c]
                note[c] = ret

        return ret

BMW WARNING

• Bulletin

本文首发于 skyline.show 欢迎访问，
文章实时更新，如果有什么错误或不严谨之处望请指出，十分感谢。
如果你觉得有用，欢迎到Github仓库点亮⭐️。

I am a bucolic migant worker but I never walk backwards.

• Material

参考资料如下列出，部分引用可能遗漏或不可考，侵删。

63.不同路径-ii

• Warrant

本文作者： Skyline(lty)

文章链接：http://www.skyline.show/力扣题解 63-不同路径-ii.html

授权声明： 本博客所有文章除特别声明外， 均采用 CC BY - NC - SA 3.0 协议。 转载请注明出处！