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 = [ * (ups+1) for _ in range(1+rights)] for i in range(1,rights+1): dp[i] = 1 for j in range(1, ups+1): dp[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)