Algorithm-Interview-Prep/8-1.py at main · caseyjkey/Algorithm-Interview-Prep · GitHub

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
36
37
38
39
40
41
42
43
44
45
46
47
# Hop either 1 2 or 3 steps up N steps, how many paths are there?

def count_steps(n, memo):
    if memo[n] != 0:
        return memo[n]
    return count_steps(n - 1, memo) + count_steps(n - 2, memo) + count_steps(n - 3, memo)

def count(n):
    memo = [0 for i in range(n + 1)]
    memo[0] = 1
    memo[1] = 1
    memo[2] = 2
    memo[3] = 4
    if memo[n] == 0:
        memo[n] = count_steps(n - 1, memo) + count_steps(n - 2, memo) + count_steps(n - 3, memo)
    return memo[n]


# 5 steps
# 4 - 3 - 2
# 3/2/1 - 2/1/0 - 1/0
# 2/1/0 - 1/0 - 0 -- 1/0 - 0 -- 0
# 1/0 - 0 -- 0 -- 0
# 0
# 13 paths

# 3 steps
# 2 - 1 - 0
# 1/0 - 0
# 0
# 4 paths

# 2 steps
# 1/0
# 0
# 2 paths

# 1 step
# 0
# 1 path

# 0 step
# 1 path (do nothing)


print(count(5))