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)

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.

StackExchange Code Review Q#152837, answer score: 4