[Leetcode][python]Unique Paths/Unique Paths II
[Leetcode][python]Unique Paths/Unique Paths II
蛮三刀酱
发布于 2019-03-26 16:19:24
发布于 2019-03-26 16:19:24
Unique Paths
题目大意
机器人从起点到终点有多少条不同的路径，只能向右或者向下走。
解题思路
动态规划 由于只能有向下向右，只有从[1][1]开始的格子需要选择走法，第一行和第一列所有都只有一种走法，所有都设置成1，（这里图方便所有都初始化为1），然后循环计算出所有其他的。
dp[j][i] = dp[j - 1][i] + dp[j][i - 1]代码
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [[1 for __ in range(n)] for __ in range(m)]
# print dp
for i in range(1, n):
for j in range(1, m):
dp[j][i] = dp[j - 1][i] + dp[j][i - 1]
return dp[m - 1][n - 1]Unique Paths II
题目大意
如果道路上有障碍，机器人从起点到终点有多少条不同的路径，只能向右或者向下走。0表示道路通行，1表示有障碍。
解题思路
和上题区别仅仅是有障碍，那么有障碍的地方就是0（不可能走到），然后初始化一下第一行和第一列（若其中有障碍则之后皆为0），最后还是上题那样做。
dp[j][i] = dp[j - 1][i] + dp[j][i - 1] (s[i][j] != 1) # 无障碍
dp[j][i] = 0 (s[i][j] = 1) # 有障碍代码
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
if obstacleGrid[0][0] == 1: # 如果第一个格子有障碍，就无法走
return 0
m = len(obstacleGrid) # 纵向
n = len(obstacleGrid[0]) # 横向
dp = [[0 for __ in range(n)] for __ in range(m)] # 初始化，所有为0
# 第一个可以走设置为1
dp[0][0] = 1
# 检查第一行和第一列是否有障碍
for i in range(1, m):
dp[i][0] = dp[i - 1][0] if obstacleGrid[i][0] == 0 else 0
for j in range(1, n):
dp[0][j] = dp[0][j - 1] if obstacleGrid[0][j] == 0 else 0
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]总结
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年10月14日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录