Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間9月前 (2025/02/28 01:09)推噓1(1推 0噓 0→)

https://leetcode.com/problems/length-of-longest-fibonacci-subsequence 873. Length of Longest Fibonacci Subsequence 給你一個陣列arr，該陣列所有元素都嚴格遞增，找出一個最長子序列每個數字都是費波那契數，返回該序列的長度。思路: 姆咪卡了好久，總之就是先固定序列的後兩個數字假設位置為i和j(i>j)，然後往前找一個 k滿足: 1.arr[k] = arr[i] - arr[j] 2.k < j 所以就用一個map紀錄每個數字的索引在哪，然後固定i和j，檢查有沒有k滿足條件，有的話就把序列長度+1，用一個二維的dp[i][j]陣列保存以i和j為結尾的最長序列長，為了方便計算初始值為2，返回最大的dp[i][j]就好。 Java Code: --------------------------------------------------------- class Solution { public int lenLongestFibSubseq(int[] arr) { int res = 0; int n = arr.length; Map<Integer, Integer> indexMap = new HashMap<>(); for (int i = 0; i < n; i++) { indexMap.put(arr[i], i); } int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(dp[i], 2); } for (int i = 2; i < n; i++) { for (int j = i - 1; j >= 0; j--) { int target = arr[i] - arr[j]; if (indexMap.containsKey(target)) { int k = indexMap.get(target); if (k < j) { dp[j][i] = Math.max(dp[j][i], dp[k][j] + 1); } } res = Math.max(res, dp[j][i]); } } return res >= 3 ? res : 0; } } --------------------------------------------------------- -- 你跟我說這個我有什麼辦法 https://i.imgur.com/wb5zrOy.jpeg