# Different path for grid move

Given a m * n grids, and one is allowed to move up or right, find the different number of paths between two grid points.

My major idea is, if move r steps right, u steps up, we can find (1) solutions for r-1 steps right and u steps up, then combine with one final right step (2) solutions for r steps right and u-1 steps up, then combine with one final up step.

I use a dynamic programming matrix dp to track number of path. For example, dp[i][j] means if we move i steps right and j steps up.

Any advice on code bugs, smarter ideas in terms of algorithm time complexity or code style advice is appreciated.

def move_right_up_count(rights, ups):
dp = [[0] * (ups+1) for _ in range(1+rights)]
for i in range(1,rights+1):
dp[i][0] = 1
for j in range(1, ups+1):
dp[0][j] = 1
for i in range(1, rights+1):
for j in range(1, ups+1):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]

if __name__ == "__main__":
print move_right_up_count(2,3)

• Smarter algorithm: prove that the answer is equal to (u+r)!/(u!r!) Jan 17 '17 at 6:46
• @RazimanT.V., I agree with you the direct count method is a very cool idea, vote up. For my original code and question, do you have any comemnts? Jan 18 '17 at 7:59
• It's pretty good, you could modify it to use a 2*n array instead of m*n though Jan 18 '17 at 8:02
• @RazimanT.V., nice idea and vote up. I make improvements based on your new idea and any advice is appreciated. Refer here => codereview.stackexchange.com/questions/153012/… Jan 19 '17 at 8:36
• I added a little bit more content you may find interesting. Jan 19 '17 at 9:35

PEP 8

for i in range(1,rights+1):


You should have a single space after the comma and before rights+1:

for i in range(1, rights+1):


Taking on the advice of Raziman T. V.: you are allowed to move $u$ steps up and $r$ steps right. Now denote a move upward by u and the move to the right by r. The total number of moves is $u + r$. Next, every valid path is a string of length $u + r$ containing $u$ characters u and $r$ characters r; clearly, any such string denotes a valid path.

Now, you can permute a string of length $u + r$ in $(u + r)!$ ways. However, since all us (respectively, rs) are equal, you divide $(u + r)!$ by $u!r!$ since there is $u!$ ways to permute the subsequence of $u$ characters u and each of them are equal; same for characters r.

$$\frac{(u + r)!}{u!r!},$$

and, finally, to the code

def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)

def count_paths(r, u):
return factorial(r + u) / factorial(r) / factorial(u)


Edit

You can optimize the above a little bit:

def count_paths_v2(r, u):
min_ru, max_ru = min(r, u), max(r, u)
value = 1
for i in range(max_ru + 1, r + u + 1):
value *= i
return value / factorial(min_ru)


count_paths performs $(u + r) + u + r$ steps, and count_paths_v2 only $\min(u, r) + (r + u) - \max(r, u).$

Cleaning a bit

What comes to your version, you can write it a little bit more succintly:

def move_right_up_count(rights, ups):
grid = [[1 for _ in range(rights + 1)] for _ in range(ups + 1)]
for y in range(1, ups + 1):
for x in range(1, rights + 1):
grid[y][x] = grid[y - 1][x] + grid[y][x - 1]
return grid[-1][-1]


Hope that helps.

• Thanks coderodde, I agree with you the direct count method is a very cool idea, vote up. For my original code and question, do you have any comemnts? Jan 18 '17 at 7:59
• @LinMa No, unfortunately that's all I can say. :( Jan 18 '17 at 8:48
• It is ok, and I have make a new post for some new ideas, if you have any advice on it, it will be great. :) Refer to => codereview.stackexchange.com/questions/153012/… Jan 19 '17 at 8:37