Unique paths

main.py

from math import factorial

def uniquePathsDP(n, m):
    dp = [[0] * m for i in range(n)]
    for i in range(n):
        dp[i][0] = 1
    for j in range(m):
        dp[0][j] = 1
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    print(dp[-1][-1])

def uniquePathsMath(n, m):
    # For 7, 3: I have to take a total of 8 steps, 6 rights and 2 downs
    # for going from 1, 1 to n, m. Now, I just need to arrange RRRRRRDD
    # in as many different ways as possible. I just choose 2 downs out of
    # 8 (8C2) and the rest will be filled by rights. Or I could do 8C6 for
    # the same purpose. Generally, its just (n + m - 2) C (n - 1). (or m - 1).
    x = n + m - 2
    y = n - 1
    return factorial(x) // (factorial(y) * factorial(x - y))

Awesomeness!