Skip to content

Instantly share code, notes, and snippets.

@jesuyedavid

jesuyedavid/numWays.py

Created April 21, 2018 15:29
Show Gist options
  • Save jesuyedavid/39ccf098280890f04ffb400e4eacdff9 to your computer and use it in GitHub Desktop.
Save jesuyedavid/39ccf098280890f04ffb400e4eacdff9 to your computer and use it in GitHub Desktop.
Download ZIP
Find the number ways to traverse an mXn grid in O(min(m,n)) space.
Raw
numWays.py
def numWays(n, m):
num=[1]*min(n, m)
for i in range(max(n,m)-1):
for j in range(min(n,m)):
if j!=0:
num[j]+=num[j-1]
return(num[n-1])
print(numWays(2,5))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment