【动态规划刷题 16】最长等差数列 (有难度) && 等差数列划分 II - 子序列

1027. 最长等差数列

https://leetcode.cn/problems/longest-arithmetic-subsequence/

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], …, nums[ik] ，且 0 <= i1 < i2 < … < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

示例 1：

输入：nums = [3,6,9,12]
输出：4
解释：
整个数组是公差为 3 的等差数列。
示例 2：

输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。
示例 3：

输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

1.状态表示*
我们先试着定义一个状态转移数组：
dp[i] 表⽰：以 i 位置元素为结尾的「所有⼦序列」中，最⻓的等差序列的⻓度。
但是这⾥有⼀个⾮常致命的问题，那就是我们⽆法确定 i 结尾的等差序列的样⼦。这样就会导致我们⽆法推导状态转移⽅程，因此我们定义的状态表⽰需要能够确定⼀个等差序列：
dp[i][j] 表⽰：以 i 位置以及 j 位置的元素为结尾的所有的⼦序列中，最⻓的等差序列的⻓度。

2.状态转移方程
设 nums[i] = b, nums[j] = c ，那么这个序列的前⼀个元素就是 a = 2 * b - c 。我们
根据 a 的情况讨论：

1. a 存在，下标为 k ，并且 a < b ：此时我们需要以 k 位置以及 i 位置元素为结尾的最⻓等差序列的⻓度，然后再加上 j 位置的元素即可。于是dp[i][j] = dp[k][i] +1 。这⾥因为会有许多个 k ，我们仅需离 i 最近的 k 即可。因此任何最⻓的都可以以 k 为结尾；
2. a 存在，但是 b < a < c ：此时只能两个元素⾃⼰玩了， dp[i][j] = 2 ；
3. a 不存在：此时依旧只能两个元素⾃⼰玩了， dp[i][j] = 2 ；

优化：
⼀边 dp ，⼀边保存。这种⽅式，我们仅需保存最近的元素的下标，不⽤保存下标数组。但是⽤这种⽅法的话，我们在遍历顺序那⾥，先固定倒数第⼆个数，再遍历倒数第⼀个数。这样就可以在 i 使⽤完时候，将 nums[i] 扔到哈希表中。

3. 初始化
根据实际情况，可以将所有位置初始化为 2 。

4. 填表顺序
a. 先固定倒数第⼆个数；
b. 然后枚举倒数第⼀个数。

5. 返回值
由于不知道最⻓的结尾在哪⾥，因此返回 dp 表中的最⼤值。

代码：

 int longestArithSeqLength(vector<int>& nums) {
        int n=nums.size();
        unordered_map<int,int> hash;
        hash[nums[0]]=0;

        //表示的是以 i，j 为结尾的，最长的等差子序列的长度
        int Max=2;
        vector<vector<int>>  dp(n,vector<int>(n,2));
        for(int i=0;i<n;i++)//先固定倒数第二个位置
        {
            for(int j=i+1;j<n;j++)//在固定倒数第一个位置
            {
                int a=2*nums[i]-nums[j];
                if(hash.count(a)&&hash[a]<i)
                   dp[i][j]=dp[hash[a]][i]+1;

                 Max=max(Max,dp[i][j]);
            }
            hash[nums[i]]=i;
        }
        return Max;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/

给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。

如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。

例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
再例如，[1, 1, 2, 5, 7] 不是等差序列。
数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。

例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。
题目数据保证答案是一个 32-bit 整数。

示例 1：

输入：nums = [2,4,6,8,10]
输出：7
解释：所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
示例 2：

输入：nums = [7,7,7,7,7]
输出：16
解释：数组中的任意子序列都是等差子序列。

1.状态表示*
我们先试着定义一个状态转移数组：
dp[i] 表⽰：以 i 位置元素为结尾的「所有⼦序列」中，最⻓的等差序列的⻓度。
但是这⾥有⼀个⾮常致命的问题，那就是我们⽆法确定 i 结尾的等差序列的样⼦。这样就会导致我们⽆法推导状态转移⽅程，因此我们定义的状态表⽰需要能够确定⼀个等差序列：
dp[i][j] 表⽰：以 i 位置以及 j 位置的元素为结尾的所有的⼦序列中，等差⼦序列的个数。

2.状态转移方程
设 nums[i] = b, nums[j] = c ，那么这个序列的前⼀个元素就是 a = 2 * b - c 。我们
根据 a 的情况讨论：

1. a 存在，下标为 k ，并且 a < b ：此时我们需要以 k 位置以及 i 位置元素为结尾的最⻓等差序列的⻓度，然后再加上 j 位置的元素即可。于是dp[i][j] = dp[k][i] +1 。这⾥因为会有许多个 k ，我们仅需离 i 最近的 k 即可。因此任何最⻓的都可以以 k 为结尾；
2. b. 因为 a 可能有很多个，我们需要全部累加起来

综上， dp[i][j] += dp[k][i] + 1 。

优化：
优化点：我们发现，在状态转移⽅程中，我们需要确定 a 元素的下标。因此我们可以在 dp 之前，将
所有元素 +下标数组绑定在⼀起，放到哈希表中。这⾥为何要保存下标数组，是因为我们要统计个
数，所有的下标都需要统计。
3. 初始化
刚开始是没有等差数列的，因此初始化 dp 表为 0
4. 填表顺序
a. 先固定倒数第⼆个数；
b. 然后枚举倒数第⼀个数。

5. 返回值
我们要统计所有的等差⼦序列，因此返回 dp 表中所有元素的和。

代码：

int numberOfArithmeticSlices(vector<int>& nums) {
          int n=nums.size();

        unordered_map<long long,vector<int>> hash;
        for(int i=0;i<n;i++)
        {
            hash[nums[i]].push_back(i);
        }

        int sum=0;
        vector<vector<int>> dp(n,vector<int>(n));
        for(int j=2;j<n;j++)
        {
            for(int i=1;i<j;i++)
            {
                long long a=(long long)2*nums[i]-nums[j];
                if(hash.count(a))
                {
                        for(auto e:hash[a])
                        {
                            if(e<i) { dp[i][j]+=dp[e][i]+1;}
                            else break;
                        }
                }
                sum+=dp[i][j];
            }
        }
        return sum;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30