leetcode 446. Arithmetic Slices II - Subsequence 等差序列的数量 + 一个很值得学习的DP动态规划做法

心已赠人 2022-06-04 09:14 188阅读 0赞

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequences:

1, 3, 5, 7, 9  
7, 7, 7, 7  
3, -1, -5, -9  
The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, …, Pk) such that 0 ≤ P0 < P1 < … < Pk < N.

A subsequence slice (P0, P1, …, Pk) of array A is called arithmetic if the sequence A\[P0\], A\[P1\], …, A\[Pk-1\], A\[Pk\] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequence slices in the array A.

The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.

Example:

Input: \[2, 4, 6, 8, 10\]

Output: 7

Explanation:  
All arithmetic subsequence slices are:  
\[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\]

和上一道题[leetcode 413. Arithmetic Slices 一个很简单的DP动态规划做法][leetcode 413. Arithmetic Slices _DP]不同的是 本题允许子序列参与，所以就更加复杂了

这道题是之前那道Arithmetic Slices的延伸，但是比较简单是因为要求等差数列是连续的，而这道题让我们求是等差数列的子序列，可以跳过某些数字，不一定非得连续，那么难度就加大了，但还是需要用DP来做。我们建立一个一维数组dp，数组里的元素不是数字，而是放一个哈希表，建立等差数列的差值和其长度之间的映射。我们遍历数组中的所有数字，对于当前遍历到的数字，又从开头遍历到当前数字，计算两个数字之差diff，如果越界了不做任何处理，如果没越界，我们看dp\[i\]中diff的差值映射自增1，然后我们看dp\[j\]中是否有diff的映射，如果有的话，说明此时已经能构成等差数列了，将dp\[j\]\[d\]加入结果res中，然后再更新dp\[i\]\[d\]，这样等遍历完数组，res即为所求，我们用题目中给的例子数字\[2，4，6，8，10\]来看：

2 4 6 8 10  
**2-1** 4-1 6-1 8-1  
**2-2** 4-1 6-1  
**2-3** 4-2

最终累计出来的结果是上面红色的数字1+2+1+3=7，分别对应着如下的等差数列：

1：\[2,4,6\]

2：\[4,6,8\] \[2,4,6,8\]

1：\[2,6,10\]

3：\[6,8,10\] \[4,6,8,10\] \[2,4,6,8,10\]

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int numberOfArithmeticSlices(vector<int>& A) 
        {
            if (A.size() <= 2)
                return 0;
    
            int count = 0;
            vector<map<int, int>> dp(A.size());
            for (int i = 0; i < A.size(); i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if ((long)A[i] - (long)A[j] > INT_MAX || (long)A[i] - (long)A[j] < INT_MIN) 
                        continue;// do not ignore this step, it will help you save time & space to pass OJ.
    
                    int diff = A[i] - A[j];
                    dp[i][diff] += 1;
                    if (dp[j].find(diff) != dp[j].end()) 
                    {
                        dp[i][diff] += dp[j][diff];
                        count += dp[j][diff];
                    }
                }
            }
            return count;
        }
    };

[leetcode 413. Arithmetic Slices _DP]: http://blog.csdn.net/jackzhang_123/article/details/78751636