PROBLEM:
Consider an N by M grid. Rows are numbered 1 to N, from top to bottom. Columns are numbered 1 to M, from left to right. You are initially at cell (1, 1) and want to go to cell (N, M). From any cell you can move to the cell below it or to the cell right to it. You should never go out of the grid. At any point you should consider all the possibilities of movement with equal probability
Let P[i][j] be the probability of visiting cell (i, j). You need to calculate the sum of P[i][j] for 1 ≤ i ≤ N, 1 ≤ i ≤ M.
QUICK EXPLANATION:
Answer is N+M-1 because after sum of probabilities of all cells in same diagonal is 1.
EXPLANATION:
APPROACH 1:
Consider that you are cell (1, 1).
After 1 step, what all cells we can reach?
(0, 1) and (1, 0).
After 2 steps, what all cells we can reach?
(0, 2), (1, 1)and (2, 0).
After 3 steps, what all cells we can reach?
(0, 3), (2, 1), (1, 2)and (0, 3).
and so on.
If we go on writing like that, we end up writing the diagonals from left top to right bottom and each cell being covered once.
For example, this table shows required steps for reaching each cell.
