рекурсия на линейной комбинации python - PullRequest
Новая
       12

рекурсия на линейной комбинации python

0 голосов
/ 19 марта 2019

У меня есть вопрос для интервью:

Существует лестница с N ступенями, и вы можете подняться на любое количество ступеней из набора натуральных чисел X? Например, если X = {1, 3, 5}, вы можете подняться на 1, 3 или 5 шагов одновременно.

Я получил приведенную ниже реализацию, и, похоже, она работает.

У меня есть несколько вопросов о моем подходе:

1.Что будет обозначение Big-O для этого фрагмента кода?

2. Есть ли лучший подход, учитывающий сложность? 

def stairA(N,X):

    print("begin")
    print(N)
    print(X)
    print(len(X))
    print("end")
    total=0

    if(len(X)==0):
        print("space_Z")
        return 0

    if (len(X)>0):
        if(X[len(X)-1]>N):
            print("space_A")
            newlist = [k for k in X if k < X[len(X)-1]]
            stairA(N,newlist) #step size greater than stair number
            #stairA(N,X[:len(T)-1]) #step size greater than stair number
        if (N==1):
            if(1 in X):
                print("space_B")
                return 1

        if (N==0):
            print("space_X")
            return 1
        if (N<0):
            print("space_Y")
            return 0


        for ind,ele in enumerate(X):                          
            a=N-ele    

            stairA(a,X)#what first step we take
            total = total + stairA(a,X)#what first step we take

    return total

Результаты: 

1+1+1+1

1+2+1

1+1+2

1+3

2+1+1

2+2

3+1

Y=[3,1,2]
Y.sort()
print(Y)
stairA(4,Y)

1 Ответ

0 голосов
/ 19 марта 2019

рекурсия, так как это генерация f (N) = f (n-1) + f (n-2) + .... 

def staircase(n, X):
        if n < 0:
            return 0
        elif n == 0:
            return 1
        else:
            return sum(staircase(n - x, X) for x in X)

Динамическое программирование: 

def staircase(n, X):
    cache = [0 for _ in range(n + 1)]
    cache[0] = 1
    for i in range(1, n + 1):
        cache[i] += sum(cache[i - x] for x in X if i - x >= 0)
    return cache[n]

Я не могу понять, почему рекурсия 1 O (| X | ** N) и динамическая O (N * | X |)

...