1. 题⽬链接：413.等差数列划分
2. 题⽬描述：
3. 解法（动态规划）：
算法思路：
1. 状态表⽰：
由于我们的研究对象是「⼀段连续的区间」，如果我们状态表⽰定义成[0, i] 区间内⼀共有多 少等差数列，那么我们在分析dp[i] 的状态转移时，会⽆从下⼿，因为我们不清楚前⾯那么多 的「等差数列都在什么位置」。所以说，我们定义的状态表⽰必须让等差数列「有迹可循」，让状 态转移的时候能找到「⼤部队」。因此，我们可以「固定死等差数列的结尾」，定义下⾯的状态表 ⽰：
dp[i] 表⽰必须「以i 位置的元素为结尾」的等差数列有多少种。
2. 状态转移⽅程：
我们需要了解⼀下等差数列的性质：如果a b c 三个数成等差数列，这时候来了⼀个d ，其 中b c d 也能构成⼀个等差数列，那么a b c d 四个数能够成等差序列吗？
答案是：显然 的。因为他们之间相邻两个元素之间的差值都是⼀样的。有了这个理解，我们就可以转⽽分析我们 的状态转移⽅程了。 对于dp[i] 位置的元素nums[i] ，会与前⾯的两个元素有下⾯两种情况：
i. nums[i - 2], nums[i - 1], nums[i] 三个元素不能构成等差数列：那么以 nums[i] 为结尾的等差数列就不存在，此时dp[i] = 0 ；
ii. nums[i - 2], nums[i - 1], nums[i] 三个元素可以构成等差数列：那么以 nums[i - 1] 为结尾的所有等差数列后⾯填上⼀个 nums[i] 也是⼀个等差数列，此时 dp[i] = dp[i - 1] 。但是，因为 nums[i - 2], nums[i - 1], nums[i] 三 者⼜能构成⼀个新的等差数列，因此要在之前的基础上再添上⼀个等差数列，于是 dp[i] = dp[i - 1] + 1 。
综上所述：状态转移⽅程为： 当： nums[i - 2] + nums[i] != 2 * nums[i - 1] 时， dp[i] = 0 当： nums[i - 2] + nums[i] == 2 * nums[i - 1] 时， dp[i] = 1 + dp[i - 1]
3. 初始化：
由于需要⽤到前两个位置的元素，但是前两个位置的元素⼜⽆法构成等差数列，因此dp[0] = dp[1] = 0 。
4. 填表顺序：
毫⽆疑问是「从左往右」。
5. 返回值：
因为我们要的是所有的等差数列的个数，因此需要返回整个dp 表⾥⾯的元素之和。
C++算法代码：
class Solution
{
public:
int numberOfArithmeticSlices(vector<int>& nums)
{
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回结果
int n = nums.size();
vector<int> dp(n);
int sum = 0;
for (int 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];
}
return sum;
}
};Java算法代码：
class Solution
{
public int numberOfArithmeticSlices(int[] nums)
{
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回值
int n = nums.length;
int[] dp = new int[n];
int sum = 0;
for (int 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];
}
return sum;
}
}