文章目录
- 413. 等差数列划分
- 状态转移方程
- 完整代码
- 978. 最长湍流子数组
- 题目解析
- 状态转移方程
- f[i]状态转移方程
- g[i]状态转移方程
- 完整代码
- 139. 单词拆分
- 状态转移方程
- 初始化
- 完整代码
413. 等差数列划分
点击查看：等差数列划分
如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。
示例 1：
输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2：
输入：nums = [1]
输出：0
状态转移方程
dp[i]：表示以i位置元素为结尾的所有子数组中等差数列的个数
若ABCD为等差数列，而D与B C也能形成等差数列，ABCDE也是一个等差数列
若想求以i为结尾的所有子数组的等差数列的个数，
而子数组是连续的，想要构成等差数列，至少使i位置与 i-1和i-2位置构成等差数列
dp[i]分为两种情况
情况1：i i-1 i-2位置元素 可以构成等差数列
假设i-2位置元素为a，i-1位置元素为b，i位置元素为c
则三者之间的差值相同，即 c-b==b-a
v以a b 为结尾的等差数列 ，由于c 与a b 也能构成等差数列，所以 以 a b c 为结尾也为等差数列
而以 a b为结尾 就相当于 以 b为结尾 即dp[i-1](以i-1位置为结尾的所有等差数列的个数)
而a b c 属于等差数列 ，且不在dp[i-1]的情况之内 ，所以 需要+1
该情况下: dp[i]=dp[i-1]+1
情况2：i i-1 i-2位置元素 不构成等差数列
假设i-2位置元素为a，i-1位置元素为b，i位置元素为c
则三者之间的差值不同 即 c-b不等于b-a
因为子数组是连续的，而a b c不构成等差数列，前面构不构成等差数列就没有意义了
该情况下： dp[i]=0
状态转移方程为：
dp[i]= c-b==b-a?dp[i-1]+1:0
完整代码
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n=nums.size();
vector<int>dp(n,0);
int i=0;
int sum=0;
for(i=2;i<n;i++)
{
//状态转移方程
dp[i]=nums[i]-nums[i-1]==nums[i-1]-nums[i-2]?dp[i-1]+1:0;
sum+=dp[i];
}
//返回dp表中所有值之和
return sum;
}
};
由于等差数列要求至少有三个元素，当只有一个/两个元素时，不满足要求，所以dp[0]=0 dp[1]=0
978. 最长湍流子数组
点击查看：最长湍流子数组
给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。
如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。
更正式地来说，当 arr 的子数组 A[i], A[i+1], …, A[j] 满足仅满足下列条件时，我们称其为湍流子数组：
若 i <= k < j ：
当 k 为奇数时， A[k] > A[k+1]，且
当 k 为偶数时，A[k] < A[k+1]；
或 若 i <= k < j ：
当 k 为偶数时，A[k] > A[k+1] ，且
当 k 为奇数时， A[k] < A[k+1]。
示例 1：
输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
示例 2：
输入：arr = [4,8,12,16]
输出：2
题目解析
B的值比A大，则呈现上升趋势
C的值比B小，则呈现下降趋势
D的值比C大，则呈现上升趋势
则ABCD数组为湍流子数组
状态转移方程
dp[i]：表示 以i位置为结尾的所有子数组中，最长的湍流数组的长度
刚开始分析写出dp[i]，但是会发现湍流数组有上升和下降趋势的问题，而dp[i]无法解决，所以再次定义f[i]和g[i]
f[i]：表示以i位置为结尾的所有子数组中，最后呈现上升趋势的最长湍流数组的长度
文章出处登录后可见！
