leetcode 62 63 Unique Paths
z
 2017-12-22 14:11:34  

62. Unique Paths I

给定一个m*n的棋盘，从棋盘左上角到棋盘右下角最多有多少条路径。

每一次移动，只能向右移一格或者向下移动一格。

star
end

动态规划问题：

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

当i==0，或者j == 0时，表示在棋盘的边缘，只有向下或者向右一条路。所以dp[i][j] = 1;

63 Unique Path II

相对于上一题，增加了一个条件：给定了一个等棋盘大小的01矩阵，1表示对应位置为一个障碍位置，不能走。

同样求一共有多少条路。

start 1 0
0 0 0
0 0 0
0 1 end

当obstacleGird[i][j] == 1时，dp[i][j] = 0;

当i==0 and j==0时，dp[i][j] = 1;

当i==0时，dp[i][j] = dp[i][j-1]

当j==0时，dp[i][j] = dp[i-1][j]

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if not obstacleGrid or not obstacleGrid[0]:
            return False
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 0:
                    if i==0 and j==0:
                        dp[i][j] = 1
                    elif i==0:
                        dp[i][j] = dp[i][j-1]
                    elif j==0:
                        dp[i][j] = dp[i-1][j]
                    else:
                        dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]