Count all possible paths from top left to bottom right in a m X n matrix.(in O(m) space)
1 Like
Diagonal movements allowed?
Yes it will form a dp and obstacles also included.
Well, in O(M*N) space it seems easy, if we assume that only movements allowed are bottom and right, and that you cannot retrace your path again.
We make a 2-D dp table where dp[i][j] stores number of ways to reach that cell. You can reach a cell from its top and left cell only (if only bottom and right movements allowed), and its easy to visualise the expression (Not giving cause you only asked for a hint). Take care of base cases though!!
EDIT: This method assumes that there arent any obstacles. But I think only a slight change is needed to include obstacles as well (Thankful if anyone can confirm!!)
how to do in O(m)
There are obstacles? Meaning certain cells arent allowed to visit?
Actually, I just checked it out myself cause I have no idea about O(M). But they have given a direct formula on how to calculate number of ways (just a formula mention 
)
Yes I practiced a similar queestion on SPOJ.We will assign 0th row to 0,0th column to zero and form a DP.checking for obstacles also.
Can you give link to that Q. Looks fun 
Should we store the array in row major order?
It should be O(m) space.I m sorry for that
Well, one thing is that you need O(MN) space to store the array itself.
Else, if you see closely, the answer is same for every array of size MxN. It doesn’t depend on array/array elements. Perhaps we can derive the formula and answer in O(1) time and O(1) space.
But specifically O(M) isnt striking me at the moment
To solve this in \mathcal{O}(n \times m) memory, you can make a DP table such that dp[i][j] denotes the numbers of ways to reach [i][j]
Then, the base cases will be:
dp[i][0] = 1 for 0\ <=\ i\ < n
dp[0][j] = 1 for 0\ <=\ j\ < m
And, the recurrence relation will be:
dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]
Note that the answer for i^{th} row depends on only 2 rows: i^{th} row and (i-1)^{th} row.
Thus we can compress the table to a 2\ - row table by taking 1^{th} row as the current row and 0^{th} row as the previous row. This solution will take \mathcal{O}(m) memory.
The obstacle condition can be also be added easily.
See the following code for implementation details.
1 Like
Thats pretty nice. I was thinking on similar lines, but went on for columns.
1 Like