Different path for grid move (part 2) 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 pre_row) and 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 &gt; 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)
The code has a bug: Since you are appending elements, you have to make sure that the array is empty in the beginning. So the cur_row = [] command should be inside the loop.

Also, the number of ways to reach origin from origin is 1. Hence pre_row should have all elements 1 initially. This means that you can just do pre_row = [1] * (ups+1) instead of appending.

Next problem is kind of aesthetic. You are building cur_row at each step and turning pre_row into it in the end. Then it makes sense to fill cur_row before the loop as well, and that will make sure that the code also works for rights == 0.

Once we do these, there is no longer the need to append to cur_row inside the loop. We are sure that the list has the correct size so we can just assign elements.

Finally just remove the if inside the loop.

Combining these we have

def grid_move(rights, ups):
    cur_row = [1] * (ups+1)
    for r in range(1, rights+1):
        pre_row = cur_row
        cur_row[0] = 1
        for u in range(1, ups+1):
                cur_row[u] = pre_row[u] + cur_row[u-1]

    return cur_row[-1]


These should make the code more readable and efficient, and make the recurrence relation clear.