873. Length of Longest Fibonacci Subsequence
https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/
문제
풀이(Recursion - 처음 풀었을 때 (TLE))
one == 0 and two == 0일 때에는 아무 것도 없는 상태이므로 가능한 경우의 수가 Take, Non Take가 있다. Take하게 되면 one자리에 해당 숫자를 넣어주고 Non Take는 기존 그대로 호출 한다.
one != 0 and two == 0일 때에는 하나는 Take되어 있는 상태이므로 현재 값을 Take할 지 Non Take할 지 확인 한다. Take할 경우 현재값은 one자리에 기존에 one값은 two자리에 넣고 호출한다. Non Take할 경우 기존 그대로 호출한다.
else부분에는 one, two값이 있을 때 실행되는데 이제부터 피보나치 조건을 확인해야 한다. 만약 피보나치 조건에 맞는다면 해당값을 one에 넣어주고 one값은 two자리에 넣어준다.
반면에 피보나치 조건에 맞지 않는다면 포인터만 1증가 시킨다.
아무래도 cache 인자로 해당 값을 넣어 주었기 때문에 TLE가 발생하였다.
풀이(Recursion)
처음 풀었던 풀이는 len(arr) 요소들 하나씩 확인하였는데 다음 피보나치 숫자가 arr안에 있는지 없는지 확인하는 것으로 변경하였다.
즉 arr = [1,3,7,11,12,14,18]에서 (1,7)이라면 다음 피보나치 숫자는 8이 될 것인데 arr안에 없으므로 return 해주고 (1,11)이라면 다음 피보나치 숫자 12가 arr안에 있으므로 (11, 12)를 arr안으로 찾는 방법으로 변경하였다.
dp 딕셔너리에 dp[(value)] = index 형식으로 저장해둔다. 그리고 키포인트로 value값으로 cache하는 것이 아닌 index로 cache하여서 TLE문제를 해결하였다.
결과(Recursion)
