• API
• FAQ
• Tools
• Archive
SHARE
TWEET

Untitled

a guest Sep 17th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # you can write to stdout for debugging purposes, e.g.
2. # print("this is a debug message")
3.
4. def fib(N):
5.     F = [0, 1]
6.     while F[-1] < N:
7.         F.append(F[-1] + F[-2])
8.     return F
9.
10. def solution(A):
11.     # write your code in Python 3.6
12.     F = fib(len(A)+1)
13.     steps = [-1] * (len(A) + 1)
14.     for f in F[1:]:
15.         if f - 1 == len(A) or f - 1 < len(A) and A[f-1] == 1:
16.             steps[f-1] = 1
17.     if steps[-1] != -1:
18.         return steps[-1]
19.     for i in range(0, len(A)):
20.         if steps[i] != -1:
21.             for f in F[2:]:
22.                 if i + f > len(A): break
23.                 if i + f == len(A) or A[i+f] == 1:
24.                     if steps[i+f] == -1:
25.                         steps[i+f] = steps[i] + 1
26.                     else:
27.                         steps[i+f] = min(steps[i+f], steps[i] + 1)
28.     return steps[-1]
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top