---

1.最长等差数列

1.题目链接

• 最长等差数列

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • dp[i]：以i位置元素为结尾的所有的子序列中，最长的等差子序列的长度 -> 无法正确表示状态
      • 因为虽然可以找到i前一个值，但是却无法得知此时它前一个数是什么，此时的公差应该是多少，现在的规模是如何
    • dp[i][j]：以i位置以及j位置的元素为结尾的所有的子序列中，最长的等差子序列的长度(i < j)

  • 推导状态转移方程
    

  • 优化：因为可能有重复元素，但是只取重复元素的最后一个元素，此时为了便于找到每个要找到的元素，有两个方案可供选择

    1. 在dp之前，将所有元素 + 下标绑定，放在哈希表中<元素, 下标数组>
       • 可行，但是效率仍不高，如果重复元素多的夸张，时间复杂度也可能逼近$O(N)$
    2. 一边dp，一边保存离它最近的元素的下标<元素， 下标>
       • 既可以保证前面的元素都放进哈希表里
       • 也可以保证如果有重复元素，那么也被最近的一个元素覆盖掉了

  • 初始化：vector<vector<int>> dp(n, vector<int>(n, 2))

  • 确定填表顺序：有两种方案可供选择，但是第一种方案在本题中，并不可取

    1. 先固定最后一个数，再枚举倒数第二个数
       • 此方案不可行，因为如果后枚举倒数第二个数，那么相对它而言，它的最近元素就不固定了
    2. 先固定倒数第二个数，再枚举最后一个数
       • 此时相对第二个数，前面最近的元素在本轮中，就是固定的

  • 确定返回值：dp表里的最大值：ret < 3 ? 0 : ret

---

3.代码实现

int longestArithSeqLength(vector<int>& nums) 
{
    unordered_map<int, int> hash; // <nums[i], i>
    hash[nums[0]] = 0;

    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, 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.count(a)) // 已经包含了判断 k < i
            {
                dp[i][j] = dp[hash[a]][i] + 1;
                ret = max(ret, dp[i][j]);
            }
        }

        hash[nums[i]] = i; // 存入当前下标，对应下一次的最近元素的下标
    }

    return ret;
}

---

2.[等差数列划分 II - 子序列]

1.题目链接

• 等差数列划分 II - 子序列

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • dp[i]：以i位置的元素为结尾的所有子序列中，等差子序列的个数 -> 无法正确表示状态
      • 因为虽然可以找到i前一个值，但是却无法得知此时它前一个数是什么，此时的公差应该是多少，现在的规模是如何
    • dp[i][j]：以i位置的元素y以及j位置的元素为结尾的所有的子序列中，等差子序列的个数(i < j)

  • 推导状态转移方程

    • dp[i][j] += dp[k][i] + 1
      

  • 优化：在dp之前，将<元素, 下标数组>绑定在一起，放进哈希表中

  • 初始化：vector<vector<int>> dp(n, vector<int>(n))

    • dp表里的值全部初始化为0

  • 确定填表顺序：固定倒数第一个数，枚举倒数第二个数

  • 确定返回值：dp表里面所有元素的和

---

3.代码实现

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

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

    vector<vector<int>> dp(n, vector<int>(n));

    int ret = 0;
    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& k : hash[a])
                {
                    if(k < i)
                    {
                        dp[i][j] += dp[k][i] + 1;
                    }
                }
            }

            ret += dp[i][j];
        }
    }

    return ret;
}