This is a continued discussion from (Different path for grid move) to optimize for space complexity, and since it is new code and I make a new post.
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 method to track count in
r-1 steps (using
r steps (using
cur_row). Here is my code and any advice on code bugs, performance improvements in terms of time complexity, or code style issues are appreciated.
Source code in Python 2.7,
def grid_move(rights, ups): pre_row =  pre_row.append(0) # initialize for zero right and up only for i in range(1, ups+1): pre_row.append(1) cur_row =  for r in range(1, rights+1): for u in range(0, ups+1): if u > 0: cur_row.append(pre_row[u] + cur_row[-1]) else: cur_row.append(1) pre_row = cur_row return cur_row[-1] if __name__ == "__main__": print grid_move(2,3)