1. 解题思路
这一题相较于上一题就直接很多了，就是一个动态规划，直接写就行了。
2. 代码实现
给出python代码实现如下：
MOD = 10**9+7
class Solution:
def uniquePaths(self, grid: List[List[int]]) -> int:
n, m = len(grid), len(grid[0])
DIRECTION = {
0: (1, 0), 1: (0, 1)}
@lru_cache(None)
def dp(i, j, direction):
if i == n-1 and j == m-1:
return 1
if i < 0 or i >= n or j < 0 or j >= m:
return 0
if grid[i][j] == 0:
return (dp(i+1, j, 0) + dp(i, j+1, 1)) % MOD
while 0 <= i < n and 0 <= j < m and grid[i][j] == 1:
direction = 1-direction
dx, dy = DIRECTION[direction]
i, j = i+dx, j+dy
return dp(i, j, direction) % MOD
return dp(0, 0, 0)
提交代码评测得到：耗时耗时2733ms，占用内存306.37MB。