[릿코드 873] Length of Longest Fibonacci Subsequence (파이썬/python)

https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/description/

Length of Longest Fibonacci Subsequence - LeetCode

 

 

디피는 확실히 복잡한듯...
재귀로도 풀어보고 여러방법으로 풀어봤는데

연속되는 피보나치에 대한 구현법에 애를 많이먹었습니다...

 

a -> b -> c 가 피보나치일때

a 까지의 가장 긴 서브 피보나치가 있다면

그 수만큼 b -> c 에 더해줍니다.

 

a 까지의 가장 긴 서브 피보나치가 없다면
b -> c 는 3입니다 (작은 값 부터 반복문을 돌렸을 뿐더러 a->b->c 인 3가지 크기밖에 경우의 수가 없음)

from typing import List


class Solution:

    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        dp = {}
        # 파이썬 Set 은 해시태이블로 구현되어있어서 in 연산시 시간복잡도가 O(1)
        s = set(arr)
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                if arr[j] - arr[i] < arr[i] and arr[j] - arr[i] in s:
                    dp[arr[i], arr[j]] = dp.get((arr[j] - arr[i], arr[i]), 2) + 1

        return max(dp.values() or [0])