-
Notifications
You must be signed in to change notification settings - Fork 0
/
num_paths.py
35 lines (32 loc) · 1.03 KB
/
num_paths.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Given a number 1 <= n <= 100 which represents a grid size of n-1 x n-1
# Find the number of paths from (0,0) to (n-1,n-1)
# You can't go across the diagonal of the grid as shown below (can't land on O's)
# O O O X
# O O X X
# O X X X
# X X X X
# n = 4 example
def num_of_paths_to_dest(n):
# paths = [] # [“EEENNN”, “EENENN”, “ENEENN”, “ENENEN”, “EENNEN”]
count = 0
def num_of_paths_helper(i, j):
if i == 0 and j == 0:
nonlocal count # python 3 feature, if we're in python 2 we'll need to keep a list
count += 1
else:
if j <= i:
# if we're here, we're on a diagonal space, can only go down
if i - 1 < j:
num_of_paths_helper(i, j - 1)
else:
# check if we can go up
if j > 0:
num_of_paths_helper(i, j - 1)
# check if we can go right
num_of_paths_helper(i - 1, j)
num_of_paths_helper(n-1, n-1)
return count
# Tests
print(num_of_paths_to_dest(6))
print(num_of_paths_to_dest(17))
print(num_of_paths_to_dest(1))