题目描绘:题目链接
题目中需要求解一个数组中等差数组的个数,这个问题可以利用动态规划的思路来分析。
三步骤:
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;
}
}