http://tafakuri.net/?p=66
def num_paths_to_grid_bottom(numRowCells, numColumnCells):
currRow = [1 for x in range(numColumnCells + 1)]
# the number of nodes to consider = numRowCells + 1
for numRow in range(1, numRowCells + 1):
for numColumn in range(1,
(m+n)C(n)
On Thu, Feb 21, 2013 at 1:26 PM, shady sinv...@gmail.com wrote:
Given a matrix of size mXn, find the number of paths from the top left
cell to the bottom right cell.
BFS is one way... any other approach ?
--
You received this message because you are subscribed to the Google
How did you directly arrive at that solution ? Can you please explain
On Thu, Feb 21, 2013 at 1:52 PM, Gaurav Rana gauravran...@gmail.com wrote:
(m+n)C(n)
On Thu, Feb 21, 2013 at 1:26 PM, shady sinv...@gmail.com wrote:
Given a matrix of size mXn, find the number of paths from the top left
Assuming that u can either move down or right,
Using Dynamic Programming,
a DP equation can be framed like this : Paths[i][j] = paths[i][j-1] +
paths[i-1][j]
By filling the entire matrix, result will be in Paths[m-1][n-1].
--
You received this message because you are subscribed to the Google
number of ways to choose n right selections out of total (n+m)
selection.(m+n)C(n)
On Thu, Feb 21, 2013 at 2:29 PM, Karthikeyan V.B kartmu...@gmail.comwrote:
Assuming that u can either move down or right,
Using Dynamic Programming,
a DP equation can be framed like this : Paths[i][j] =
+1 for above approach , its called memotization .. it helps reducing
redundant recursive call for the same matter.
On Thu, Feb 21, 2013 at 2:29 PM, Karthikeyan V.B kartmu...@gmail.comwrote:
Assuming that u can either move down or right,
Using Dynamic Programming,
a DP equation can be framed
No. of paths =(n+m-2)C(n-1)
Total number of times u have to change the column is m-1 and row is n-1
thus u have total (n-1+m-1) operations to do and out of these operations u
have to choose n-1 operation for changing rows.
ok.
On Thu, Feb 21, 2013 at 2:29 PM, Karthikeyan V.B
If the allowable moves are : one step towards Right, and one step towards
bottom
Explanation for (m+n) C n: you may represent the path using a String
consisting of only R and D,
where R is a right move and D is a downward move. To go from (1,1) to (m,n)
the length of the string
will be (m+n) as
Well, (m+n) C (n) is the answer only in the case the allowable moves are :
one step towards Right, and one step towards bottom.
On Thu, Feb 21, 2013 at 2:05 PM, shady sinv...@gmail.com wrote:
How did you directly arrive at that solution ? Can you please explain
On Thu, Feb 21, 2013 at 1:52
Given a matrix of size mXn, find the number of paths from the top left cell
to the bottom right cell.
BFS is one way... any other approach ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving
10 matches
Mail list logo
