InBit/FibonacciSteps.py at master · kpandya3/InBit · 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
48
49
50
# You are climbing a stair case. Each time you can either make 1 step or 2 steps.
# The staircase has n steps. In how many distinct ways can you climb the staircase ?

# steps(n) to take n steps in singles/doubles

_cache = {
	0: 0,
	1: 1
}

def steps(n):
	if n in _cache:
		return _cache[n]

	for i in xrange(2, n+1):
		_cache[i] = _cache[i - 1] + _cache[i - 2] + 2

	return _cache[n]

print steps(1)
print steps(2)
print steps(3)
print steps(4)

# allSteps = []

# _cache = {
# 	0: "",
# 	1: "1"
# }

# def steps(n, stepsSoFar=""):
# 	if n in _cache:
# 		stepsSoFar += _cache[n]
# 		allSteps.append(stepsSoFar)

# 	for i in xrange(2, n + 1):
# 		_cache[i] = 0

# 		for j in [1, 2]:
# 			if _ca

# 	stepsSoFar2 = stepsSoFar
# 	stepsSoFar += "1"
# 	steps(n-1, stepsSoFar)
# 	stepsSoFar2 += "2"
# 	steps(n-2, stepsSoFar2)

# steps(3)
# print(allSteps)