pythonSnippets/climbingStairsModified.py at main · dangerousLefty/pythonSnippets · 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
"""This file is for blah blah blah """

#climbing stairs with k steps
def climbingStairs(k: int, n:int) -> int:
    if n < 2:
        return 1
    stepArr = [1 for i in range(n+1)]
    stepArr[0] = 1
    stepArr[1] = 1

    for i in range(2,n+1):
        combinations = 0
        for j in range(1,k+1):
            if j > i:
                break

            combinations += stepArr[i-j]

        stepArr[i] = combinations

    return stepArr[n]

def climbingStairsKstepsOptimized(k: int, n:int) -> int:
    if n < 2:
        return 1
    stepArr = [0 for i in range(k)]
    stepArr[0] = 1
    stepArr[1] = 1

    for i in range(2,n+1):
        comb = 0
        for j in range(1,k+1):
            if i - j < 0:
                continue
            comb += stepArr[(i-j)%k]

        stepArr[i%k] = comb


    return stepArr[n % k]

def climbingStairsRedSteps(k: int, n: int, stairs: [bool]) -> int:
    if n < 2:
        return 1
    stepArr = [0 for i in range(k)]
    stepArr[0] = 1
    #stepArr[1] = 1

    for i in range(1,n+1):
        comb = 0
        for j in range(1,k+1):
            if i - j < 0:
                continue

            if stairs[i-j] == True:
                #stepArr[i%k] = 0
                comb += 0

            else:
                comb += stepArr[(i-j)%k]

        stepArr[i%k] = comb


    return stepArr[n % k]


#a = climbingStairs(3,5)
#a = climbingStairsKstepsOptimized(2,5)
steps = [False, True, False, True, True, False, False]
a = climbingStairsRedSteps(3,7,steps)