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