GFG 8 Unique paths in a grid

You are given a matrix grid of n x  m size consisting of values 0 and 1. A value of 1 means that you

can enter that cell and 0 implies that entry to that cell is not allowed [Note: The  rst and last cell

of the grid can also be 0].

You start at the upper-left corner of the grid (1, 1) and you have to reach the bottom-right corner

(n, m) such that you can only move in the right or down direction from every cell.

Your task is to calculate the total number of ways of reaching the target modulo (10 +7).

Example 1:

Input:

n = 3, m = 3

grid[][] = {{1, 1, 1};

 {1, 0, 1};

 {1, 1, 1}}

Output:

2

Explanation:

1 1 1

1 0 1

1 1 1

This is one possible path.

1 1 1

1 0 1

1 1 1

This is another possible path.

9

---------

dfs又超时了，所以就用动态规划来做了。