Loading... 最近在Leetcode着重刷了动态规划的题目，感觉形式确实多种多样，但做多了发现有一些规律，所以写下此篇博客来进行归纳总结,重点讲递推方程推导思路。 ## 线性DP ## 序列DP ### 定义序列范围（开头结尾，最后两个...） 1. **最长的斐波那契子序列的长度** <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-03-05-135510.png" alt="image-20230305215504097" style="zoom:50%;" style=""> 思路：**怎么样固定一个斐波那契数列->知道其开头两个数或者末尾两个数**->为什么不开头两个数？顺序不对，确定开头得知道后面的序列情况，而后面序列情况在当前求取之后->定义以j和i为结尾序列，dp[i\][j\]表示以arr[j\]和arr[i\]结尾的序列的最大斐波那契数列长度->怎么找前面?哈希表，即递推方程**dp[i\][j] = Math.max(3, dp[j\][map.get(t)] + 1)** ->优化：即使前面都是数列内容也比答案小的，下一个值大于arr[j]的。 代码： ```java class Solution { public int lenLongestFibSubseq(int[] arr) { int n = arr.length; int res = 0; int[][] dp = new int[n][n]; Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < n; i++) map.put(arr[i], i); for(int i = 0; i < n; i++){ for(int j = i - 1; j >= 0 && j + 2 > res; j--){ int t = arr[i] - arr[j]; if(t >= arr[j]) break; if(map.containsKey(t)) dp[i][j] = Math.max(3, dp[j][map.get(t)] + 1); res = Math.max(dp[i][j], res); } } return res; } } ``` 最后修改：2023 年 03 月 06 日 © 允许规范转载 赞 3 如果觉得我的文章对你有用，请随意赞赏
1 条评论
动态规划哎，学到了学到了