1. 最长定差子序列 

1218. 最长定差子序列

状态表示：

dp[i] 表示以 i 位置为结尾的所有子序列中，最长等差数列的长度

状态转移方程：

枚举到 i 位置时，需要在之前找到一个元素 b 来保证 a - b = diff，距离 a 最近的 b 所具有的等差数列的长度肯定比之前的大或者等于，所以只需要找到这个位置的 dp 值即可，然后 + 1 就是 dp[i] 的值

但是用上面的方法会超时，所以可以考虑做一个优化，通过哈希表来把 b 的值和对应的 dp 值存入到哈希表中，这样就可以直接通过线性的时间复杂度直接找到 b 对应的 dp 值，又由于哈希表不能存储重复元素的特性，后续存储的 b 会把之前的覆盖掉，之后找到的 b 就是距离 a 最近的

还可以优化的是，既然 b 都可以放到哈希表中了，那么 a 也可以放到哈希表中，之后直接在哈希表中做动态规划

在动态规划之前，还需要把 （arr[0] ，1）放到哈希表中

class Solution {
    public int longestSubsequence(int[] arr, int diff) {
        HashMap<Integer,Integer> hash = new HashMap<>();
        hash.put(arr[0],1);
        int ret = 1;
        int n = arr.length;
        for(int i = 1;i < n;i++){
            hash.put(arr[i],hash.getOrDefault((arr[i] - diff),0) + 1);
            ret = Math.max(hash.get(arr[i]),ret);
        }
        return ret;
    }
}

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

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

状态表示：

如果还按照之前的经验以 dp[i] 来表示枚举到 i 位置时的最长斐波那契子序列的长度的话，在找到前一个位置（用 j 表示）时，dp[j] 前面的数字还是不确定是什么，但是如果知道 i , j 位置的值的话，就可以确定前一个位置的值，所以使用一维 dp 表是不够的

dp[i][j]：表示以 i 和 j 位置为结尾的所有子序列中最长的斐波那契子序列的长度

状态转移方程：

通过 i , j 两个位置的值就可以确定前一个值，假如前一个值在 k 位置，那么就是 dp[j][i] = dp[k][j] + 1，找不到的话序列长度为 2，不能构成斐波那契子序列，不能更新答案

初始化：可以把 dp 表中全部初始化为 2

填表顺序：从左到右

返回值：最后结果只需要在 dp 表中找到最大值即可

此外，还可以做一个优化，每次都需要在前面的区间内找 a ，可以把原来数组的值和下标映射到哈希表中，查询的话直接取就行

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        HashMap<Integer,Integer> hash = new HashMap<>();
        for(int i = 0;i < arr.length;i++){
            hash.put(arr[i],i);
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                dp[i][j] = 2;
            }
        }
        int ret = 2;
        for(int i = 2;i < n;i++){
            for(int j = 1;j < i;j++){
                int a = arr[i] - arr[j];
                if(a < arr[j]&&hash.containsKey(a)){
                    dp[j][i] = dp[hash.get(a)][j] + 1;
                }
                ret = Math.max(ret,dp[j][i]);
            }
        }
        return ret == 2 ? 0 : ret;
    }
}

3. 最长等差数列

1027. 最长等差数列

状态表示：

先来尝试还按照之前的状态表示一样，用 dp[i] 来表示以 i 位置为结尾的所有子序列中，最长的等差数列的长度，但是此时填表的话会发现，前一个位置的 dp 值是不能确定公差为多少的，只是表示了一个长度，所以一维的 dp 表不行，需要使用二维 dp 表

dp[i][j] 表示以 i 位置和 j 位置元素为结尾的所有子序列中，最长的等差序列长度

状态转移方程：

和上一题一样，通过两个元素就可以确定上一个元素了，由于计算出来的 a 的位置可能出现在前面也可能出现在后面，而真正需要的是离 b 最近的那个，所以还需要使用哈希表来存储下标的映射关系，但是如果存在很多 a 的值，那么时间复杂度就又退化为了 O(n^3)，可以边做 dp 边存储哈希表，确保存储进去的都是最近的 a

初始化：所有值都初始化为 2

填表顺序：由于需要确定距离 b 最近的 a，如果还是按照上一题的方法，固定 j 移动 i 的话，k 的位置是不断变化的，很难确定 k 的位置，如果反过来，固定 i ，移动 j ，那么再获取 k 的位置就是距离 b 最近的了

返回值：所有 dp 值中的最大值

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][1001];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = 1;
            }
        }
        int res = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int d = nums[i] - nums[j] + 500;
                dp[i][d] = dp[j][d] + 1;
                res = Math.max(res, dp[i][d]);
            }
        }
        return res;
    }
}

4. 等差数列划分 II - 子序列

446. 等差数列划分 II - 子序列

状态表示：

和上一题一样，使用一维的 dp 表是不能来表示出之前的等差数列的，还是要使用二维 dp 表

dp[i][j] 表示以 i ，j 位置为结尾的子序列中等差数列的个数

状态转移方程：

如果能找到一个 k 位置的数 a 符合等差数列的数时，那么 dp[i][j] 就加上 dp[k][i] + 1，这里的加一是因为 k ， i 位置为结尾的等差子序列没有包含 k , i , j 这种情况

和上一题一样，还是通过把值和下标映射存储在哈希表中提升查询效率，由于可能存在多个 a 的情况，所以需要用一个数组来存储下标

初始化：由于只有 3 个符合条件的子序列才是等差数列，所以可以把所有的 dp 值都初始化为 0

填表顺序：这一题就可以固定 j ，然后往前枚举 i 了，

返回值：所有的 dp 和