一个机器人位于一个 m × n 的网格左上角(1,1)，每次只能向下或向右移动一步，目标是到达右下角（m,n）。网格中的某些格子是障碍物（用1表示），机器人不能进入障碍物格子。空位置用0表示。

请计算机器人从起点到终点共有多少条不同的路径（路径中不能经过任何障碍物）。答案保证小于等于2 × 10^9。

第一行包含两个整数m和n，表示网格的行数和列数。 接下来m行，每行n个整数（0或1），表示网格中的障碍物分布。

输出一个整数，表示从左上角到右下角的不同路径总数。若无法到达，输出0。

样例1解释：

3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

数据范围

• 1 ≤ m, n ≤ 100。

• grid[i][j] 为 0 或 1。

• 答案 ≤ 2 × 10^9

力扣

动态规划