忙。。后两题先跳过
62.不同路径
- 题目链接：62.不同路径
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp=[[0 for a in range(n)] for b in range(m)]
print(dp)
dp[0][0]=1
for i in range(m):
for j in range(n):
if j-1>=0 and i-1>=0:
dp[i][j]=dp[i][j-1]+dp[i-1][j]
elif j-1<0 and i-1>=0:
dp[i][j]=dp[i-1][j]
elif i-1<0 and j-1>=0:
print(i,j)
dp[i][j]=dp[i][j-1]
else:
continue
return dp[m-1][n-1]
63. 不同路径 II
- 题目链接：63. 不同路径 II
- 某处有障碍，则到达某处的方法为0
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m=len(obstacleGrid)
n=len(obstacleGrid[0])
if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:
return 0
dp = [[0 for i in range(n)]for j in range(m)]
dp[0][0]=1
for i in range(m):
if obstacleGrid[i][0] == 0:
dp[i][0] = 1
else:
break
for j in range(n):
if obstacleGrid[0][j] == 0:
dp[0][j] = 1
else:
break
for k in range(1, m):
for l in range(1, n):
if obstacleGrid[k][l]:
continue
else:
dp[k][l]=dp[k-1][l] + dp[k][l-1]
return dp[m-1][n-1]
