2022-07-09

[Zheaoli]

2022-07-09

[dreamhunter2333]

#
# @lc app=leetcode.cn id=873 lang=python3
#
# [873] 最长的斐波那契子序列的长度
#

from typing import List

# @lc code=start
class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        res = 0
        n = len(arr)
        dp = [[0] * n for _ in range(n)]
        cahce_map = {
            arr[i]: i
            for i in range(n)
        }

        for i in range(1, n):
            for j in range(i-1, -1, -1):
                if arr[i] - arr[j] >= arr[j]:
                    break
                if arr[i] - arr[j] not in cahce_map:
                    continue
                k = cahce_map[arr[i] - arr[j]]
                dp[i][j] = max(dp[j][k] + 1, 3)
                res = max(res, dp[i][j])

        return res

# @lc code=end
print(Solution().lenLongestFibSubseq([1, 2, 3, 4, 5, 6, 7, 8]))
print(Solution().lenLongestFibSubseq([1, 3, 7, 11, 12, 14, 18]))

---

微信id: 而我撑伞 来自 vscode 插件

[SaraadKun]

873. 最长的斐波那契子序列的长度

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length, ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], i);
        }
        //dp[j][i] j < i, 代表以j, i结尾的数列最大长度
        int[][] dp = new int[n][n];
        for (int i = 2; i < n; i++) {
            //arr严格递增,要保证存在target < j,则arr[i] - arr[j] < arr[j]
            for (int j = i - 1; j > 0 && arr[j] * 2 > arr[i]; j--) {
                int target = map.getOrDefault(arr[i] - arr[j], -1);
                if (target >=0) {
                    dp[j][i] = Math.max(dp[target][j] + 1, 3);
                }
                ans = Math.max(ans, dp[j][i]);
            }
        }
        return ans;
    }
}

---

WeChat: Saraad

[SaraadKun]

797. 所有可能的路径

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    //使用双端队列来当做栈,方便添加进结果集
    ArrayDeque<Integer> deque = new ArrayDeque<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        //DFS 
        deque.offer(0);
        dfs(graph, 0, graph.length);
        return ans;
    }

    private void dfs(int[][] graph, int idx, int n) {
        if (idx == n - 1) {
            ans.add(new ArrayList<>(deque));
            return;
        }
        for (int p : graph[idx]) {
            deque.addLast(p);
            dfs(graph, p, n);
            deque.pollLast();
        }
    }
}

---

WeChat: Saraad