Leetcode——413. 等差数列划分

时间:2022-12-21 15:27:20

题目描绘:题目链接

题目中需要求解一个数组中等差数组的个数,这个问题可以利用动态规划的思路来分析。

三步骤:

1:问题归纳。题目需要求解等差数列的和,我们可以用一个数组保存前i个元素可以构成的等差数列的个数。dp[ i ],最后需要的时候再求和。

2:递归关系式的书写:等差数列无非要满足这个关系:a[ i ] - a[i-1] = a[i-1] - a[i-2];如果再添加一个元素a[i+1]满足:a[i+1] - a[i] = a[i] - a[i -1],则只需要在前者的基础上加1就可以。

  递推关系:dp[i] = dp[i-1]+1

3:初始化:满足dp[0] = 0;dp[1] = 0.

代码如下:

class Solution {
public int numberOfArithmeticSlices(int[] A) {
if(A == null || A.length == 0){
return 0;
}
int len = A.length;
int[] a = new int[len];
for(int i = 2; i < len; i++){
if(A[i] - A[i-1] == A[i-1]-A[i-2]){
a[i] = a[i-1] + 1;
}
}
      //最后求和
int sum = 0;
for(int t: a){
sum += t;
}
return sum;
}
}