电视台视频网站建设方案中国新冠疫情最新消息
个人主页：元清加油_【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
解法
算法原理与解析
我们这题使用动态规划，我们做这类题目可以分为以下五个步骤
- 状态显示
- 状态转移方程
- 初始化（防止填表时不越界）
- 填表顺序
- 返回值
- 状态显示
dp[i][j] 表⽰：以 i 位置以及 j 位置的元素为结尾的所有的⼦序列中，等差⼦序列的个 数。规定⼀下 i < j 。
- 状态转移方程
设 nums[i] = b, nums[j] = c ，那么这个序列的前⼀个元素就是 a = 2 * b - c 。我们根据 a 的情况讨论：
- a 存在，下标为 k ，并且 a < b ：此时我们知道以 k 元素以及 i 元素结尾的等差序列的个数 dp[k][i] ，在这些⼦序列的后⾯加上 j 位置的元素依旧是等差序列。但是这⾥会多出来⼀个以 k, i, j 位置的元素组成的新的等差序列，因此 dp[i][j] = dp[k][i] + 1 ；
- 因为 a 可能有很多个，我们需要全部累加起来。
综上， dp[i][j] += dp[k][i] + 1。
- 初始化（防止填表时不越界）
刚开始是没有等差数列的，因此初始化 dp 表为 0 。
- 填表顺序
- 先固定倒数第⼀个数；
- 然后枚举倒数第⼆个数。
- 返回值
我们要统计所有的等差⼦序列，因此返回 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;}
};