Return to Revisions

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 = [1] * (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)