https://leetcode.com/problems/arithmetic-slices/description/
解题思路:
-
首先判断其可用动态规划解决
-
when array[i] - array[i - 1] == array[i - 1] - array[i - 2]
dp[i] = dp[i - 1] + 1;
result += dp[i]
代码如下:
class Solution {
public int numberOfArithmeticSlices(int[] A) {int len = A.length; if(len < 3) return 0; int[] dp = new int[len]; if(A[2] -A[1] == A[1]-A[0]) dp[2] = 1; int res = dp[2]; for(int i = 3; i < len; i++){ if((A[i] - A[i - 1]) == (A[i - 1] - A[i - 2])) dp[i] = dp[i - 1] + 1; res += dp[i]; } return res;
}
}
网友评论