This is a continued discussion from (Different path for grid move 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 > 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)
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 > 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)
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 > 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)
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 > 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)