This is a continued discussion from (Different path for grid move (part 2)) to optimize for space complexity (using only
cur list, other than a
cur and another
pre lists), 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.
Source code in Python 2.7,
def grid_move_v2(rights, ups): cur =  * (ups + 1) for r in range(1, rights+1): for u in range(1, ups+1): cur[u] = cur[u] + cur[u-1] return cur[-1] if __name__ == "__main__": print grid_move_v2(2,3) print grid_move_v2(4,2)