动规解决等差数列划分leetcode413

思路：连续数组元素问题，根据教训，不能用深搜去解决，此题可以用动规。

动规五部曲：

1.dp数组含义；

2.初始化dp；

3.递推公式

4.遍历顺序

5.打印dp【调试用】

该题的重点在于如何判断是不是等差数组：学过等差数列的人应该都知道，不赘述

那关键就在于如何设置dp以及递推公式了：

按照以往一贯套路：dp[i] 表示以 下标 i 结尾的元素 所在数组中等差数组个数；

判断条件：一个是当前数组是等差数列，一种是当前数组不构成等差数列

递推公式：如果构成了等差数列，下一次的等差数组个数可能会加一，即dp[i]=dp[i-1]+1；

如果不构成，下一次等差数组的个数可能和这一次的一样：dp[i]=dp[i-1]+0;

遍历顺序：从前往后

代码：

class Solution {
public:
int num=0;
bool flag;
    int numberOfArithmeticSlices(vector& nums) {
        if(nums.size()<3)return 0;
        //dp[i]:以 下标 i 结尾的 含有等差数组的个数
        vectordp(nums.size());
        //初始化
        dp[0]=0;dp[1]=0;
        //递推公式：
        
        //循环：从前往后
        for(int i=2;i