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. OK, I Understand
 
Top