C++刷leetcode（413. 等差数列划分）【动态规划】
本帖最后由 糖逗 于 2020-4-20 12:21 编辑题目描述：
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
如果满足以下条件，则称子数组(P, Q)为等差数组：
元素 A, A, ..., A, A 是等差的。并且 P + 1 < Q 。
函数要返回数组 A 中所有为等差数组的子数组个数。
示例:
A =
返回: 3, A 中有三个子等差数组: , 以及自身 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/arithmetic-slices
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
int numberOfArithmeticSlices(vector<int>& A) {
int len = A.size();
if(len < 3) return 0;
int dp;
dp = 0;
dp = 0;
int sum = 0;
for(int i = 2; i < len; i++){
if(A - A == A-A){
dp = dp + 1;
sum += dp;
}
else{
dp = 0;
}
}
return sum;
}
注意事项：
1.可以想到dp = dp + 1;，sum += dp;并没有发现，可能需要自己画图找规律。 注意这道题并不是指所有子区间，而是有连续序列号的子区间！ 数列的定义本身就是连续的数字序列 jkluoling1992 发表于 2020-4-20 12:22
数列的定义本身就是连续的数字序列
我是指从原序列取数的时候数必须要连续紧挨着取。
比如1 2 3 4 2 5 1 最后结果是3，虽然1， 3， 5是等差序列但是在原来的序列中是不连续的所以不算。最后得到的子序列是【1,2,3】、【2,3,4】、【1,2,3,4】 糖逗 发表于 2020-4-20 12:28
我是指从原序列取数的时候数必须要连续紧挨着取。
比如 最后结果是3，虽然1， 3， 5是等差序列但是在原 ...
{:10_254:}是的，是子串的概念了 jkluoling1992 发表于 2020-4-20 12:34
是的，是子串的概念了
刚查了一下子串的定义：串中任意个连续的字符组成的子序列称为该串的子串
（ps：以前以为不连续的也是子串{:10_245:}你说的是对的{:10_275:}） 糖逗 发表于 2020-4-20 12:38
刚查了一下子串的定义：串中任意个连续的字符组成的子序列称为该串的子串
（ps：以前以为不连续的也是 ...
letcode刷了几道题就看不下去了{:10_266:}，坚持不下去，游戏太香了{:10_254:} jkluoling1992 发表于 2020-4-20 12:41
letcode刷了几道题就看不下去了，坚持不下去，游戏太香了
为了以后有更多的游戏打，现在要努力刷题{:10_266:}工作不好找呀{:10_266:}（社会人流下了悲痛的泪水{:10_266:}） 糖逗 发表于 2020-4-20 12:46
为了以后有更多的游戏打，现在要努力刷题工作不好找呀（社会人流下了悲痛的泪水{:10 ...
哈哈哈，原来都是社会中人哈{:10_279:} 糖逗 发表于 2020-4-20 12:46
为了以后有更多的游戏打，现在要努力刷题工作不好找呀（社会人流下了悲痛的泪水{:10 ...
难受......
上网课的时候刷力扣，看完里面的题目，乖乖的回去上网课了{:10_277:} _2_ 发表于 2020-4-28 09:37
难受......
上网课的时候刷力扣，看完里面的题目，乖乖的回去上网课了
leetcode刷题前可以先看看《大话数据结构》，一开始不会可以先看看题解，看考哪些知识点然后可以去B站找对应知识点自学。自学差不多一开始刷都这样，我也不是没道题都能做出来的，看题解勉强刷下去。其实我建议你刷题先刷专项，比如动态规划标签下的题，刷完了一个系列再刷另一个系列会更好一些。 糖逗 发表于 2020-4-28 10:55
leetcode刷题前可以先看看《大话数据结构》，一开始不会可以先看看题解，看考哪些知识点然后可以去B站找 ...
蟹蟹{:10_254:}
学生刷题实属不易{:10_243:}
页:
[1]