파이썬에서 n까지 더할 피보나치 수의 최소 수를 찾는 프로그램은 무엇입니까?

<시간/>

숫자 n이 있다고 가정합니다. 합이 n이 되는 데 필요한 최소 피보나치 수를 찾아야 합니다.

따라서 입력이 n =20과 같으면 출력은 3이 됩니다. 피보나치 수 [2,5, 13]를 사용하여 합이 20이 되기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

해상도 :=0
fibo :=값이 [1, 1]인 목록
fibo <=n의 마지막 요소인 동안 do
- x :=fibo의 마지막 두 요소의 합
- fibo에 x 삽입
- n이 0이 아닌 동안 수행
  - fibo> n의 마지막 요소인 동안 수행
    - fibo에서 마지막 요소 삭제
  - n :=n - fibo의 마지막 요소
  - 해상도 :=해상도 + 1
반환 해상도

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시

class Solution:
   def solve(self, n):
      res = 0
      fibo = [1, 1]
      while fibo[-1] <= n:
         fibo.append(fibo[-1] + fibo[-2])

      while n:
         while fibo[-1] > n:
            fibo.pop()
         n -= fibo[-1]
         res += 1
      return res

ob = Solution()
n = 20
print(ob.solve(n))