Different path for grid move (part 3) 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)
Since you never use r you can shift it down by one and call it _ (the customary unused variable in Python).

def grid_move_v2(rights, ups):
    cur = [1] * (ups + 1)
    for _ in range(rights):
        for u in range(1, ups+1):
            cur[u] = cur[u] + cur[u-1]
    return cur[-1]