LeetCode刷题--- 等差数列划分 II - 子序列

个人主页：元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归题

 http://t.csdnimg.cn/yUl2I

【C++】    

​​​​​​http://t.csdnimg.cn/6AbpV

数据结构

​​​http://t.csdnimg.cn/hKh2l

---

前言：这个专栏主要讲述动态规划算法，所以下面题目主要也是这些算法做的  

我讲述题目会把讲解部分分为3个部分：
1、题目解析

2、算法原理思路讲解

3、代码实现

---

等差数列划分 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：

输入：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  <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1

---

解法

算法原理与解析

我们这题使用动态规划，我们做这类题目可以分为以下五个步骤

1. 状态显示
2. 状态转移方程
3. 初始化（防止填表时不越界）
4. 填表顺序
5. 返回值

• 状态显示

dp[i][j] 表⽰：以 i 位置以及 j 位置的元素为结尾的所有的⼦序列中，等差⼦序列的个 数。规定⼀下 i < j 。

• 状态转移方程

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

1. a 存在，下标为 k ，并且 a < b ：此时我们知道以 k 元素以及 i 元素结尾的等差序列的个数 dp[k][i] ，在这些⼦序列的后⾯加上 j 位置的元素依旧是等差序列。但是这⾥会多出来⼀个以 k, i, j 位置的元素组成的新的等差序列，因此 dp[i][j] = dp[k][i] + 1 ；
2. 因为 a 可能有很多个，我们需要全部累加起来。

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

• 初始化（防止填表时不越界）

刚开始是没有等差数列的，因此初始化 dp 表为 0 。

• 填表顺序

1. 先固定倒数第⼀个数；
2. 然后枚举倒数第⼆个数。

• 返回值

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

---

代码实现

class Solution {
public:
typedef long long ll;int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();// 优化unordered_map<ll, vector<int>> hash;for (int i = 0; i < n; i++){hash[nums[i]].push_back(i);}vector<vector<int>> dp(n, vector<int>(n));		// 创建 dp 表int sum = 0;for (int j = 2; j < n; j++)						// 固定倒数第一个数{for (int i = 1; i < j; i++)					// 枚举倒数第二个数{ll a = (ll)nums[i] * 2 - nums[j];		// 处理数据溢出if (hash.count(a)){for (auto k : hash[a]){if (k < i){dp[i][j] += dp[k][i] + 1;}else break;}}sum += dp[i][j];}}return sum;}
};