Different path for grid move

Question

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)

• Raziman T V: Smarter algorithm: prove that the answer is equal to (u+r)!/(u!r!)
• Lin Ma: @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?
• Raziman T V: It's pretty good, you could modify it to use a 2*n array instead of m*n though
• Lin Ma: @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/…
• coderodde: I added a little bit more content you may find interesting.

Answer 1

PEP 8

PEP 8 complains about this line:

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):

Straight to business

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.

The above leads to

$$\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.

• Lin Ma: 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?
• coderodde: @LinMa No, unfortunately that's all I can say. :(
• Lin Ma: 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/…