只差一点点

这就是最好的时代

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

分类于

题目：等差数列划分 II - 子序列

给你一个整数数组 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：

1
2
3
4
5
6
7
8
9
10
输入：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：

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

提示：

1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1

分析：

给定数组为[1,2,3,4,5]，求等差子数组，我们使用动态规划的过程，一次遍历：

遍历到3，发现它跟[1,2]可以组成子数组[1,2,3]，满足等差子数组要求，记dp[3]=1。

遍历到4，发现它跟[2,3]可以组成子数组[2,3,4]，满足等差子数组要求，而它的前一位即3本来就有一个等差子数组，我们在它的基础上可以延续出来一个新的等差子数组[1,2,3,4]，所以，dp[4]=dp[3]+1=2，dp[3]表示原来3的基础上延续出来的[1,2,3,4]，+1表示全新的[2,3,4]。

遍历到5，发现它跟[3,4]可以组成子数组[3,4,5]，满足等差子数组要求，而它的前一位即4本来是有两个等差子数组，我们在它的基础上可以延续出来两个新的等差子数组分别为[1,2,3,4,5]和[2,3,4,5]，所以，dp[5]=dp[4]+1=3，解释同上。
这样，我们把dp[3]+dp[4]+dp[5]=1+2+3=6就是答案。

方法一、动态规划
好了，本题还是以[1,2,3,4,5]为例，[1,3,5]也是一个合格的答案，所以，我们可以转换成昨天的题目，我们求出每一个以nums[i]结尾的公差d的元素个数，再按照上述求等差子数组的思路很容易求出以nums[i]结尾等着为d的等差子数组的数量，把所有这些等差d加一起就是以nums[i]结尾的等差子序列的数量，列举所有的i即可求得结果，所以，我们定义如下：

状态定义：dp[i][d]表示以nums[i]结尾，公差为d的等差子数组的数量。

状态转移：dp[i][d]=dp[j][d]+1，其中j表示以nums[i]结尾等着为d的前面那个数nums[j]的下标。

这样定义看似没有问题，实际运行的过程其实是有问题的：

问题一：以[1,2,3,4,5]为例，遍历到2（下标为1）的时候，它与下标0的元素1的差值为1，按照公式应该得到：dp[1][1]=dp[0][1]+1=1,但是这个结果并不符合题目的要求，题目要求长度至少为3，那么，我们怎么才能知道下标j前面还有没有元素呢？如果只有[nums[j], nums[i]]是无法满足长度3的要求的。
问题二：以[7,7,7,7,7]为例，遍历到第4个7（下标为3）的时候，它的等差子序列有4个，分别为[7(0),7(1),7(3)]、[7(0),7(2),7(3)]、[7(1),7(2),7(3)]、[7(0),7(1),7(2),7(3)]，按照dp[i][d]=dp[j][d]+1的规则去计算也是不对的。
似乎没有思路了。再仔细想一下，既然三个长度的子序列是由两个长度的子序列升级来的，那么，我们能不能在统计结果的时候从两个长度的子序列开始计算呢，这样，三个长度的子序列就不用计算了。比如，以[1,2,3,4,5]为例：

遍历到2时，以2结尾的子序列只有一个，即[1,2]，我们记为dp2=1。
遍历到3时，以3结尾的子序列有三个，分别为[1,2,3]、[1,3]、[2,3]，我们分别记为dp[3][1]=dp[2][1]+1=2和dp[3][2]=dp[1][2]+1=1，可以看到，只有dp[2][1]升级上来的那个子序列才可以作为结果，所以，我们在这里ans += dp[2][1]。
遍历到4时，以4结尾的子序列有多少个呢？它与前面元素的公差分别有1、2、3，我们按照公式可得dp[4][1]=dp[3][1]+1=3、dp[4][2]=dp[2][2]+1=1、dp[4][3]=dp[1][3]+1=1，一共五个，分别是[1,4]、[2,4]、[3,4]、[2,3,4]、[1,2,3,4]，可以看到，只有dp[3][1]升级上来的那两个子序列才满足条件，所以，ans += dp[3][1]。
再来看看[7,7,7,7,7]这种特殊用例，遍历到第4个7的时候，它与前面任意元素的差值都是0，按照前面的公式dp[i][0]=dp[j][0]+1就不行了，这时候我们可以换成累加就可以轻松解决了，dp[i][0]+=dp[j][0]+1。

最后，题目限定nums[i]的范围为-2^31 <= nums[i] <= 2^31 - 1，有可能溢出，而且，我们也不知道等差d有多少个，所以，使用HashMap来存储key为公差的等差子数组数量。

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    //动态规划，vector<map<int, int>> dp(n)
    //dp[j][diff]表示以 nums[j] 为结尾、 diff 为等差数的等差序列个数
    int numberOfArithmeticSlices(vector<int> &nums) {
        const int n = nums.size();
        int ans = 0;
        vector<unordered_map<long long, int>> dp(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                long long diff = 1ll * nums[i] - nums[j]; //差值
                auto it = dp[j].find(diff);  //查找这个地方是否有差值满足条件
                int cnt = it == dp[j].end() ? 0 : it->second; //没有记录0，有则取出
                ans += cnt;  //放入答案
                dp[i][diff] += cnt + 1; //此位置为原位置 + 1，下次取出时会直接放入答案
            }
        }
        return ans;
    }
};

感想：

第一眼就是动态规划，可是dp数组的含义没有确定好，也找不准状态转移方程，导致写了一大片冗余且错误的代码。

看了官方题解才恍然大悟，评论区有一个观点也让我受益良多：动态规划就是逆向反推，又最后需要求得的答案反推到前面的转移方程。看似自底向上从无到有，实则逆向反推寻找来路