等差数列划分 II - 子序列(动态规划)

等差数列划分 II - 子序列(动态规划)如果一个数列至少有三个元素 并且任意两个相邻元素之差相同 则称该数列为等差数列 例如 以下数列为等差数列 1 3 5 7 9 7 7 7 7 3 1 5 9 以下数列不是等差数列 1 1 2 5 7 数组 A 包含 N 个数 且索引从 0 开始 该数组子序列将划分为整数序列

大家好,我是讯享网,很高兴认识大家。

如果一个数列至少有三个元素,并且任意两个相邻元素之差相同,则称该数列为等差数列。

例如,以下数列为等差数列:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。

1, 1, 2, 5, 7

数组 A 包含 N 个数,且索引从 0 开始。该数组子序列将划分为整数序列 (P0, P1, …, Pk),P 与 Q 是整数且满足 0 ≤ P0 < P1 < … < Pk < N。

如果序列 A[P0],A[P1],…,A[Pk-1],A[Pk] 是等差的,那么数组 A 的子序列 (P0,P1,…,PK) 称为等差序列。值得注意的是,这意味着 k ≥ 2。

函数要返回数组 A 中所有等差子序列的个数。


讯享网

输入包含 N 个整数。每个整数都在 -231 和 231-1 之间,另外 0 ≤ N ≤ 1000。保证输出小于 231-1。

示例:

输入:[2, 4, 6, 8, 10]

输出:7

解释:
所有的等差子序列为:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
1e3的数据量,很容易想到两重循环去实现动态规划。
dp[i][j]代表的是以i结尾的差值为j的等差数组的长度。
例如:[1, 1, 2, 3, 4, 5]
在这里插入图片描述
代码如下:

#define LL long long class Solution { 
    public: int numberOfArithmeticSlices(vector<int>& A) { 
    int n = A.size(); LL ans = 0; vector<map<LL,int>> p(n); for (int i = 1; i < n; i++) { 
    for (int j = 0; j < i; j++) { 
    LL delta = (LL)A[i] - (LL)A[j]; int sum = 0; if (p[j].find(delta) != p[j].end()) { 
    sum = p[j][delta]; } p[i][delta] += sum + 1; ans += sum; } } return (int)ans; } }; 

讯享网

dp是永远的痛。
努力加油a啊,(o)/~

小讯
上一篇 2025-01-23 16:05
下一篇 2025-01-10 23:41

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/79923.html