动态规划---子序列专题

介绍子序列

子序列就是从一个数组中连续的抽取或者不连续的抽取元素，但是子序列中的相对位置不能改变，例如，nums={1,2,3,4}，{1,2,3}或者{1,2,4}都是子序列，但是{2,1,3}就不是子序列了，因为在nums中，2本来是在1的后面的，而在{2,1,3}中，2跑到1的前面了，其相对位置发生了改变，所以{2,1,3}不是子序列

1.最长递增子序列---非常经典的题

题目链接： 300. 最长递增子序列 - 力扣（LeetCode）

题目解析：找出nums数组中的最长严格递增的子序列，并返回其长度，注意是严格递增的子序列，也就是说明该子序列中不能由重复的元素

算法讲解：动态规划

1.状态表示：经验+题目要求

经验还是来套路，以末位置为结尾，再根据题目中要求找子序列，所以我们就还要找到子序列，所以状态表示可以这样表示：

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

2. 状态转移方程

此时推算子序列问题的状态转移方程，也是可以分为两种情况去分析的，分别是子序列长度为1或者子序列长度大于1的这两种情况

第一种情况：子序列的长度等于1

当子序列的长度等于1时，也就代表nums数组中第i个位置的数据单独作为一个子序列，此时子序列的最长长度就是1了，所以此时dp[i]=1

第二种情况：子序列的长度大于1

当子序列的长度大于1时，此时就不单单是nums[i]单独一个数据作为子序列了，此时子序列可能是nums[i]与以nums[i-1]为结尾的最长递增子序列合并共同构成子序列，也可能是与nums[i-2]为结尾的最长递增子序列合并共同构成子序列，也可能是与nums[i-3]为结尾的最长递增子序列等等情况，也就是说明nums[i]有可能与位置i前面的任何一个子序列合并共同构成子序列，此时为了方便叙述，我们用j表示i位置前面的位置，此时j是大于等于0并小于等于i-1的

此时根据上面的分析，来推算状态转移方程，因为nums[i]可能会与以nums[j](0<=j<=i-1)为结尾的子序列，因为我们要求的是最长的递增子序列，所以此时就要知道以nums[j]（注意这里的nums[j]不是单单代表一个数据，是代表[0,i-1]区间中的数据）的元素为结尾的所有子序列中，最长子序列递增的长度，根据状态表示，可以用dp[j]来表示以位置j为结尾的所有所有子序列中，最长递增子序列的长度，则此时dp[i]=Math.max(dp[i],dp[j]+1)

3.初始化

此时可以将dp表中所有的数据初始化为最坏的情况，也就是1

4.填表顺序

从左往右填dp表

5.返回值

返回dp表中的最大值

代码实现：

class Solution {public int lengthOfLIS(int[] nums) {int n=nums.length;int[] dp=new int[n];for(int i=0;i<n;i++){dp[i]=1;}int ret=1;for(int i=1;i<n;i++){for(int j=i-1;j>=0;j--){if(nums[j]<nums[i]){dp[i]=Math.max(dp[i],dp[j]+1);}}if(ret<dp[i]) ret=dp[i];}return ret;}
}

2.最长递增子序列的个数

题目链接：673. 最长递增子序列的个数 - 力扣（LeetCode） 

讲解这道题之前，先来讲解一个小算法，如何用一次for循环来找出数组中最大数的出现次数，此时只要分别定义一个max变量来记录最大值，一个变量count来记录max的出现次数，此时在遍历数组的过程中，当nums[i]==max时，就让max++，当nums[i]<max时，就啥也不做，当nums[i]>max时，此时就要更新max和count的值，一句话总结，就是边找边记录

代码实现：

public static void main(String[] args) {int[] nums={1,2,2,2,3,2,3,1,1,3};int max=nums[0];int count=1;for (int i=1;i<nums.length;i++){if(nums[i]==max){count++;}else if(nums[i]>max){max=nums[i];count=1;}}System.out.println("max："+max+"出现的次数："+count);}

题目解析：返回nums数组中的最长子序列的个数

算法讲解：动态规划

1.状态表示：经验+题目要求

因为题目要求计算nums数组中的最长子序列的个数，所以可以这样定义状态表示：

dp[i]表示：以i位置元素为结尾的所有子序列中，最长递增子序列的个数 

但是这样是不够的，因为题目要求的是最长子序列的个数，所以还要知道最长子序列的长度呀，所以，此时还要定义一个状态表示来表示子序列的最长长度，此时就会有两个状态表示：

len[i]表示：以i位置元素为结尾的所有子序列中，最长子序列的长度

count[i]表示：以i位置元素为结尾的所有子序列中，最长子序列的个数 

2.状态转移方程 

此时要求最长子序列的长度，还要求最长子序列出现的次数，此时就可以按照上面讲的拿到算法思想，边找边记录，所以此时，可以一起来推算len[i]和count[i]的状态转移方程，此时还是可以分为两种情况去讨论

第一种情况：子序列的长度为1

如果子序列的长度为1，那么就是nums[i]单独构成一个子序列，此时len[i]=count[i]=1

第二种情况：子序列的长度大于1

如果此时子序列的长度大于1，那么就是nums[i]与前面的子序列合并构成一个子序列，此时要找的是递增子序列，所以要在nums[j]>nums[i]的前提下进行

则此时在推算len[i]和count[i]时，跟一开始讲的那道题的算法思想一样，此时就会遇到3中情况

第一种情况：len[j]+1==len[i]

此时说明len[i]依旧是最长子序列的长度，所以此时让count[i]+=count[j] 

第二种情况：len[j]+1<len[i]

此时啥都不用做

第三种情况：len[j]+1>len[i]

此时说明最长子序列的长度就不是len[i]了，而是len[j]+1了，所以此时要将len[i]=len[j]+1和count[i]=count[j] 

总结如下图

3.初始化

此时可以将两个表的数据初始化为最坏的情况，也就是1

4.填表顺序

从左往右填两个表即可

5.返回值

依旧是上面那道题的算法思想，边找边记录

代码实现

class Solution {public int findNumberOfLIS(int[] nums) {int n=nums.length;int[] len=new int[n];int[] count=new int[n];for(int i=0;i<n;i++) len[i]=count[i]=1;int maxLength=1,ret=1;for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(nums[i]>nums[j]){if(len[j]+1==len[i]){count[i]+=count[j];}else if(len[j]+1>len[i]){len[i]=len[j]+1;count[i]=count[j];}}}if(maxLength==len[i]) ret+=count[i];else if(maxLength<len[i]){maxLength=len[i];ret=count[i];}}return ret;}
}

3.摆动序列 

题目链接：376. 摆动序列 - 力扣（LeetCode） 

什么是摆动序列呢？数据呈现一升一降趋势的就是摆动序列，如下图的五种情况

题目解析：返回nums数组中最长摆动子序列的长度

算法讲解：动态规划

1.状态表示：经验+题目要求

 因为题目要求返回最长摆动子序列的长度，一开始可能就会这样定义状态表示，

dp[i]表示：以i位置元素为结尾的所有子序列中，最长摆动序列的长度

但是单单这样一个状态表示是无法解决问题的，因为要找的摆动序列，此时判断是否要依据i位置前面的摆动序列最后一段的变化趋势，而最后一段的变化趋势会有两种情况，分别是上升和下降这两种情况，所以可以定义两个状态表示：

f[i]表示：以i位置元素为结尾的所有子序列中，最后一段为“上升”趋势的最长摆动序列的长度

g[i]表示：以i位置元素为结尾的所有子序列中，最后一段为“下降”趋势的最长摆动序列的长度 

2.状态转移方程

因为状态表示有两个，所以推算状态转移方程时也要分别讨论

推算f[i]

推算f[i]时，此时子序列会分为两种情况，分别是子序列长度等于1和子序列长度大于1的情况

第一种情况：子序列的长度等于1

如果子序列的长度等于1，那么就代表nums[i]单独一个元素作为子序列，则此时f[i]==1

第二种情况：子序列的长度大于1

如果子序列的长度大于1，那么就代表nums[i]是与以[0,i-1]位置区间元素为结尾的子序列合并构成子序列，此时用一个变量j来代表[0,i-1]位置的情况

因为f[i]是代表最后一段为“上升”趋势的最长摆动序列的长度，所以此时要在nums[j]<nums[i]的条件下推算f[i]，如果我们还要求出最长长度且还是摆动序列，此时求f[i]就要知道以j位置为结尾的所有子序列中，最后一段为“下降”趋势的最长摆动序列的长度，此时就可以用g[j]来表示，此时g[i]+1==f[i]了

推算g[i]

推算g[i]时，此时子序列会分为两种情况，分别是子序列长度等于1和子序列长度大于1的情况

第一种情况：子序列的长度等于1

如果子序列的长度等于1，那么就代表nums[i]单独一个元素作为子序列，则此时g[i]==1

第二种情况：子序列的长度大于1

如果子序列的长度大于1，那么就代表nums[i]是与以[0,i-1]位置区间元素为结尾的子序列合并构成子序列，此时用一个变量j来代表[0,i-1]位置的情况

因为g[i]是代表最后一段为“下降”趋势的最长摆动序列的长度，所以此时要在nums[j]>nums[i]的条件下推算g[i]，如果我们还要求出最长长度且还是摆动序列，此时求f[i]就要知道以j位置为结尾的所有子序列中，最后一段为“上升”趋势的最长摆动序列的长度，此时就可以用f[j]来表示，此时f[i]+1==g[i]了

3.初始化

可以将f表和g表初始化为最坏的情况，也就是1

4.填表顺序

从左往右填即可

5.返回值

返回f表和g表的最大值即可

代码实现

class Solution {public int wiggleMaxLength(int[] nums) {int n=nums.length;int[] f=new int[n];int[] g=new int[n];int ret=1;for(int i=0;i<n;i++){f[i]=1;g[i]=1;}for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(nums[i]>nums[j]){f[i]=Math.max(g[j]+1,f[i]);}else if(nums[i]<nums[j]){g[i]=Math.max(f[j]+1,g[i]);}}ret=Math.max(ret,Math.max(f[i],g[i]));}return ret;}
}

4.最长数对链 

题目解析：返回能构成的最长对数链的长度

算法讲解：

1.状态表示：经验+题目要求

dp[i]表示：以第i个数对为结尾的所有数对链中，最长数对链的长度

2.状态转移方程

在推算状态转移方程时，依旧是根据第i个位置来研究，之前在对第i个位置来研究时，是可以保证倒数第2个元素是在i位置前面的，但是这道题，倒数第2个元素可能出现在i位置的后面，所以此时要根据数对中的第1个元素进行升序的排序，这样就可以保证倒数第二个元素就一定在i位置的前面了，分析如下图

假设上图是已经排好序的情况，此时c>=a的，在根据数对的定义，此时d>c的，所以此时d>a，此时根据数对链的定义，此时第i个位置的数对无法和后面的数对构成数对链，此时就可以保证数链对中的倒数第2个数据是i位置前面的

此时得知要排序的原因后，就可以推算状态转移方程了

根据第i个位置的数对研究问题，此时以第i个数对为结尾的数对链有两种情况，分别是数对链长度为1和数对链长度大于1的情况

第一种情况：数对链的长度等于1

此时就是第i为位置上的数对单独作为数对链，此时数对链的最大长度等于1，即dp[i]=1

第二种情况：数对链的长度大于1

此时就是第i个数与前面的数对链合并作为以第i个位置为结尾的最长数对链，用变量j来表示i位置前面的情况，此时要求dp[i]，就要知道i位置前面最长的数对链长度，此时可以用dp[j]来表示以第j个数对为结尾的最长数对列长度，则此时dp[i]=Math.max(dp[j]+1,dp[i])

3.初始化

此时可以将dp初始化最坏的情况，也就是1

4.填表顺序

根据状态转移方程，从左往右填表即可

5.返回值

返回dp表中的最大值即可，可以一边填表一边寻找最大值

代码实现：

class Solution {public int findLongestChain(int[][] pairs) {int h=pairs.length;int[] dp=new int[h];for(int i=0;i<h;i++){dp[i]=1;}//排序Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));int ret=1;for(int i=1;i<h;i++){for(int j=0;j<i;j++){if(pairs[j][1]<pairs[i][0]){dp[i]=Math.max(dp[j]+1,dp[i]);}}ret=Math.max(ret,dp[i]);}return ret;}
}

5.最长定差子序列 

题目链接：1218. 最长定差子序列 - 力扣（LeetCode） 

题目解析：返回arr数组中最长等差序列的长度

算法讲解：动态规划

1.状态表示：经验+题目要求

根据题目，可以这样定义状态表示：

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

2.状态转移方程

此时分析状态转移方程时，依旧是分为两种情况：

第一种情况：子序列的长度为1

当子序列的长度等于1，就是说明arr[i]单独作为一个等差序列，此时dp[i]=1

第二种情况：子序列的长度大于1

当子序列的长度大于1时，就是说明arr[i]会与前面的等差序列合并，形成一个新的等差数列，此时就要知道i位置前面的最长等差序列的长度，用变量j来表示i位置前面的情况，此时就可以用dp[j]来表示i位置前面的最长等差序列的长度，且因为要构成等差序列，所以要保证nums[i]-nums[j]==difference，则此时的状态转移方程为：dp[i]=Math.max(dp[j]+1,dp[i])

但是这样代码会超时，代码如下

class Solution {public int longestSubsequence(int[] arr, int difference) {int n=arr.length;int[] dp=new int[n];for(int i=0;i<n;i++) dp[i]=1;int ret=1;for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(arr[i]-arr[j]==difference) dp[i]=Math.max(dp[j]+1,dp[i]);}ret=Math.max(ret,dp[i]);}return ret;}
}

第二种分析：

因为difference是固定的，当以arr[i]为结尾的等差序列的倒数第二个元素也是固定的，此时假设b为倒数第2个元素且a为等差序列中最后一个元素，此时b==a-difference

此时a前面肯能会出现多个b，此时只要去a位置前最后一个b的就行了，因为以后面b结尾的等差子序列的长度是一定大于等于以前面b为结尾的等差序列的长度，所以此时可以用一个哈希表来记录以b为结尾的最长等差子序列的长度，哈希表的下标就是arr[i]，对应下标对应的哈希值就是以arr[i]为结尾的最长等差子序列的长度，所以此时在哈希表中做动态规划即可，甚至不用设计一个dp表

此时求hash[a]就要依靠hash[a-difference]的值，所以此时状态转移方程：

hash.put(a,hash.getOrDefault(a-difference,0)+1); 

3.初始化

先初始化哈希表

4.填表顺序

从左往右填哈希表

5. 返回哈希表中最大的值

代码实现：

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

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

题目链接：873. 最长的斐波那契子序列的长度 - 力扣（LeetCode） 

题目解析：返回arr数组中的最长斐波那契子序列的长度

1.状态表示：经验+题目要求

此时可以这样定义状态表示：

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

2.状态转移方程：

此时，还是用变量j来表示[0,i-1]位置区间的情况，此时要推算dp[i]的话，此时还要知道以arr[j]为结尾的最长斐波那契子序列的长度，根据状态表示，可以用dp[j]来表示，但是在这道题中，还要涉及到j位置前面的元素，因为要满足形成斐波那契数列的条件，此时j位置前面的数可以通过arr[i]-arr[j]来解决，此时用a来表示arr[j]-arr[i]，也就是说，当arr[i]和arr[j]固定时，a是要确保是一个定值的，但是根据状态表示，dp[j]只表示以j位置为结尾的最长斐波那契子序列的长度，这个状态表示无法确定j位置前面的值，此时j位置前面的值可以是a或h或g，所以这个状态表示是不足够解决问题的

前面的一些题为什么可以设计状态表示？

因为前面的题最多就涉及到i位置前面一个元素，而这道题却设计到了i位置前面的元素和j位置前面的两个元素 

这个状态表示不可以结局问题，那就换一种状态表示，一维不够，就用二维

1.新状态表示：

可以这样定义状态表示：

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

如下图

2.推算状态转移方程：

此时，我们是根据arr[i]和arr[j]为结尾来研究问题，此时因为要找的是斐波那契子序列，所以还要找i位置前面的元素，用变量k来表示i位置前面的位置，用变量a来表示nums[j]-nums[i]

此时，推算dp[i][j]可以根据a的两种情况来分析，分别是a存在或者a不存在

第一种情况：a存在

当a存在时，由于a=arr[j]-arr[i]，此时还是有两种情况的，分别是a能与arr[i]和arr[j]构成斐波那契序列和a不能与arr[i]和arr[j]构成斐波那契序列

当a能与arr[i]和arr[j]构成斐波那契序列，也就是a<nums[i]，此时计算dp[i][j]的话，首先就要知道以a和nums[i]为结尾的最长斐波那契子序列，a就是nums[k]，此时可以用dp[k][i]来表示，此时dp[i][j]=Math.max(dp[k][i]+1,dp[i][j])

a不能与arr[i]和arr[j]构成斐波那契序列，由于dp[i][j]表示的是长度。可以将dp[i][j]=2 

第二种情况：a不存在

当a不存在时，就是没有以arr[i]及arr[j]为结尾的斐波那契序列，此时dp[i][j]=2 

小优化：

根据上面的分析的话，是要通过一个for循环来寻找a，但是此时可以将arr[i]和i存储到一个哈希表中，由于arr是严格递增的，所以arr中是不存在重复元素的 

 3.初始化

此时可以将dp初始化为最坏的情况，也就是2

但是此时有一个问题，dp[0][0]怎么办，i等于0，j也等于0，j不是要大于i的吗，其实如果根据i<j来推算dp[i][j]，此时一些dp值是用不到的，如下图，因为i<j，所以紫色框框的值是用不到的，与用到的dp值一同初始化为最坏的情况即可

4.填表顺序

因为要填dp[k][i]，在去填dp[i][j]，因为k<i，所以要从上往下的顺序填dp表

5.返回值

如果ret<3，则返回0，否则返回ret

代码实现：

class Solution {public int lenLongestFibSubseq(int[] arr) {int n=arr.length;Map<Integer,Integer> hash=new HashMap<>();int[][] dp=new int[n][n];for(int i=0;i<n;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=0;for(int j=2;j<n;j++){//先固定arr[j]for(int i=1;i<j;i++){//固定arr[i]int a=arr[j]-arr[i];if(a<arr[i]&&hash.containsKey(a)){int k=hash.get(a);dp[i][j]=Math.max(dp[k][i]+1,dp[i][j]);}ret=Math.max(ret,dp[i][j]);}}return ret>=3?ret:0;}
}

 7.最长等差数列

题目链接：1027. 最长等差数列 - 力扣（LeetCode 

题目解析：返回nums数组中的最长等差子序列的长度

算法讲解：动态规划 

状态表示：经验+题目要求

此时根据经验可以这样定义状态表示：

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

此时去根据dp[i]推算状态转移方程，首先就要知道i位置前面的最长等差子序列的长度，用变量j来表示[0.i-1]区间的位置，此时dp[j]就表示以j位置元素为结尾的所有子序列中，最长等差子序列的长度，但是此时是不能直接根据dp[j]来推算dp[i]的，因为由于dp只是定义了长度，我们并不知道等差序列长什么样，就是nums[i]可能不会与nums[j]为结尾的等差子序列构成等差序列，例如，假设nums[i]和nums[j]之间的公差为2，但是此时以nums[j]结尾的等差子序列的公差可能是3，也可能是2，也可能是其他数，如果是2，则此时nums[i]能与其构成等差子序列，如果不是2，则此时nums[i]不能与其构成等差子序列，所以此时这个状态表示是不能够解决问题的

1.新的状态表示：

一维不够，就用二维的状态表示：

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

2.状态转移方程： 

此时假设nums[i]为b，nums[j]为c，此时就可以根据b和c来推算等差子序列中的倒数第3个数，假设其为a且a的坐标为k，则a=2*c-b，此时就可以根据a的三种情况来分析问题

第一种情况：a不存在

如果a不存在的话，就说明nums数组中没有能与b和c构成等差序列的元素，此时b和c就单独构成等差子序列，则此时dp[i][j]=2;

第二种情况：a存在，但是i<=k<=j

此时如果i<=k<=j，说明b<=a<=c的，因为a是倒数第三个数，则此时a和b和c这三个数也是不能构成等差数列的，因为a是要在b的前面的

第三种情况：a存在，且a<b

如果a<b，则此时是可以构成a和b和c是可以构成等差子序列的， 此时如果要求dp[i][j]，此时就要知道以k位置及i位置为结尾的所有子序列中的最长等差子序列的长度，此时根据状态表示，其可以用dp[k][i]来表示，此时dp[i][j]=dp[k][i]+1

3.优化策略

此时还有一个问题，可能i位置前面可能存在多个a，此时只要找后面的a就行了，也就是离b最近的a，因为以后面a为结尾的等差子序列的长度是肯定大于或者等于以前面a为结尾的等差子序列的，那我们如何找这个离b最近的a呢？

如果按照平常的思路，还要通过一个for循环来寻找离b最近的a，此时时间复杂度就会高达O(N^3)，此时时非常有可能会超时的，此时有两个优化策略，都是用哈希表来实现优化的

第一个优化策略：在dp之前，将所有元素到+所有的下标绑定，放在哈希表中，此时就是<元素，下标>数组的哈希结构，但是此时这个下标数组的长度是可能非常大的，此时也会达到O(N)的复杂度，此时还是没有优化的很厉害，但是这种优化策略是可行的

第二种优化策略：一边dp一边去寻找离b最近的a，此时就是<元素，下标>的哈希结构，此时找a就会到大O(1)的时间复杂度，可以选择这个优化策略

我做题时的一个错误的优化策略：不能在dp之前元素和下标绑定到哈希表中，先假设数组如下图

4.初始化

首先将dp表中的所有数据初始化最坏情况即可，也就是2

5.填表顺序

此时有两种填表顺序

第一种填表顺序：先固定倒数第一个数，再去枚举倒数第二个数，也就是先固定nums[j]，去枚举nums[i]，但是这种填表顺序配上第二种优化策略不太友好，因为这种填表顺序，i是随时在变化的，此时就很难确定离nums[i]最近的a

第二种优化策略：先固定倒数第二个数，再去枚举倒数第一个数，也就是先固定nums[i]，去枚举nums[j]，此时i就是固定的，对第二种优化策略就很好，此时只要在进行i的下一次循环之前，将nums[i]和i绑定到哈希表中即可

6.返回值

返回dp表中的最大值即可

代码实现：

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

8.等差数列划分 II 

题目链接：446. 等差数列划分 II - 子序列 - 力扣（LeetCode） 

题目解析：返回nums数组中所有等差子序列的个数

算法讲解：动态规划 

1.状态表示：经验+题目要求

在这道题中，按照以往的经验就会这样直接定义状态表示了，dp[i]表示以i位置为结尾的所有子序列中，是等差子序列的个数，但是这样是不可以解决问题的，因为此时dp[i]表示的只有长度，按以往做题的经验，我们要通过dp[i-1]或者dp[i-1]等等的dp值来推算dp[i]的，但是此时根据这个状态表示是不可以根据dp[i-1]或者dp[i-1]等等的dp值推算出dp[i]的，因为在以i位置的元素研究问题时，此时要找出以i-1位置为结尾的所有子序列中，是等差子序列的个数，此时可以用dp[i-1]来表示，但是此时dp[i-1]只表示长度，也就是说，通过dp[i-1]，我们就知道其实一个等差序列，并不知道等差子序列的公差是多少，因为不知道公差，所以此时是无法判断nums[i]与前面的等差子序列构成等差子序列的，此时一维的状态表示解决不了问题，就通过二维的状态表示来解决问题

此时可以这样定义状态表示：

dp[i][i]表示以i位置元素及j位置元素为结尾的所有子序列中，为等差序列的个数，且i<j

2.状态转移方程

 此时还是一个变量a来表示[0,i-1]之间的元素，用变量k来表示a的下标，用变量b来表示nums[i]，用变量c来表示nums[j]，此时a=2*nums[i]-nums[j]，此时还是根据a的三种情况来划分问题

第一种情况：a不存在

当a不存在，就说明i位置前面没有能够与b和c组成等差序列的元素，此时以b和c结尾的等差序列的个数就为0，此时dp[i][j]=0

第二种情况：a存在，但i<=k

当a存在，但是由于a的k大于等于i，因为a表示的是b前面的元素，也就是说i是要小于k的，所以此时i位置前面也没有元素能够与b和c构成等差数列，此时dp[i][j]=0

第三种情况：a存在且k<i

此时这种情况是可以构成等差数列的，此时要推算dp[i][j]，此时就要知道以k位置元素及i位置元素为结尾的所有子序列中，为等差序列的个数，根据状态表示，可以用dp[k][i]来表示，此时dp[i][j]+=dp[k][i]+1

3.小优化

此时因为要dp时会用到a，按照思路直接上手写代码，就要通过一次for循环来寻找a，但是此时可以通过一个哈希表来记录a与其下标的映射关系，因为此时nums中可能存在多个a，此时是要将a的所有情况考虑进去的，所以此时哈希表的结构为<元素，下标数组>

4.初始化

此时可以将dp表中的数据全部初始化为最坏的情况，也就是0

5.填表顺序

先固定倒数第一个数，再去枚举倒数第二个数

6.返回值

返回dp表中所有数据之和

代码实现

class Solution {public int numberOfArithmeticSlices(int[] nums) {int n=nums.length;int[][] dp=new int[n][n];Map<Integer,List<Integer>> hash=new HashMap<>();for(int i=0;i<n;i++){int tmp=nums[i];if(!hash.containsKey(tmp)){hash.put(tmp,new ArrayList<Integer>());}hash.get(tmp).add(i);}int ret=0;for(int j=2;j<n;j++){for(int i=1;i<j;i++){int a=2*nums[i]-nums[j];if(hash.containsKey(a)){for(Integer k: hash.get(a)){if(k<i) dp[i][j]+=dp[k][i]+1;else break;}}ret+=dp[i][j];}}return ret;}
}

此时代码如上，此时在这道题中可能出现数据溢出的情况，且这种情况刚好称为等差序列，如下图

此时只要将Integer改为Long类型即可，

代码如下

class Solution {public int numberOfArithmeticSlices(int[] nums) {int n=nums.length;int[][] dp=new int[n][n];Map<Long,List<Integer>> hash=new HashMap<>();for(int i=0;i<n;i++){long tmp=(long)nums[i];if(!hash.containsKey(tmp)){hash.put(tmp,new ArrayList<Integer>());}hash.get(tmp).add(i);}int ret=0;for(int j=2;j<n;j++){for(int i=1;i<j;i++){long a=(long)2*nums[i]-nums[j];if(hash.containsKey(a)){for(Integer k: hash.get(a)){if(k<i) dp[i][j]+=dp[k][i]+1;else break;}}ret+=dp[i][j];}}return ret;}
}

我在解决这道题遇到的一个问题：在进行dp[i][j]+=dp[k][i]+1时，一定要判断k<i，因为在dp前，已经将所有值等于a的元素绑定到哈希表中了，此时有的a对应的下标k是有可能大于i的，k>i的a我们是不能考虑进去的，因为这样就形成不来等差子序列的