【动态规划】C++算法：446等差数列划分 II – 子序列

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

446. 等差数列划分 II – 子序列

给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。

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

例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。

再例如，[1, 1, 2, 5, 7] 不是等差序列。

数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。

例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

题目数据保证答案是一个 32-bit 整数。

示例 1：

输入：nums = [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]

示例 2：

输入：nums = [7,7,7,7,7]

输出：16

解释：数组中的任意子序列都是等差子序列。

参数范围：

1 <= nums.length <= 1000

-2³¹ <= nums[i] <= 2³¹ – 1

动态规划

时间复杂度😮(nn)

空间复杂度😮(nn)

变量解析

长度大于2的称为等差子序列，长度等于2的不妨称为“准等差”。

动态规划的细节，方便检查

两层循环，分别枚举等差数列的最后一个元素和倒数第二个元素。

代码

核心代码

class Solution {
public:
	int numberOfArithmeticSlices(vector& nums) {
		m_c = nums.size();
		vector<unordered_map> mSubCount1(m_c), mSubCount2(m_c);
		int iRet = 0;
		for (int i = 1; i < m_c; i++)
		{
			for (int j = 0; j < i; j++)
			{
				const long long sub = (long long)nums[i] - nums[j];
				if (mSubCount2[j].count(sub))
				{
					mSubCount2[i][sub] += mSubCount2[j][sub];
				}
				if (mSubCount1[j].count(sub))
				{
					mSubCount2[i][sub] += mSubCount1[j][sub];
				}
				mSubCount1[i][sub]++;				
			}
			for (const auto& [_tmp,cnt] : mSubCount2[i])
			{
				iRet += cnt;
			}
		}
		return iRet;
	}
	int m_c;
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}


int main()
{
	vector nums;
	{
		Solution sln;
		nums = { 1,1,1,1 };
		auto res = sln.numberOfArithmeticSlices(nums);
		Assert(5, res);
	}
	{
		Solution sln;
		nums = { 2, 4, 6, 8, 10 };
		auto res = sln.numberOfArithmeticSlices(nums);
		Assert(7, res);
	}
	{
		Solution sln;
		nums = { 7,7,7,7,7 };
		auto res = sln.numberOfArithmeticSlices(nums);
		Assert(16, res);
	}

	{
		Solution sln;
		nums = { 0, 2000000000, -294967296 };
		auto res = sln.numberOfArithmeticSlices(nums);
		Assert(16, res);
	}


}

可以优化掉一个变量

class Solution {

public:

int numberOfArithmeticSlices(vector& nums) {

m_c = nums.size();

vector<unordered_map> mSubCount(m_c);

int iRet = 0;

for (int i = 1; i < m_c; i++)

{

for (int j = 0; j < i; j++)

{

const long long sub = (long long)nums[i] – nums[j];

if (mSubCount[j].count(sub))

{

mSubCount[i][sub] += mSubCount[j][sub];

iRet += mSubCount[j][sub];

}

mSubCount[i][sub]++;

}

}

return iRet;

}

int m_c;

};

2023年1月版

class Solution {

public:

int numberOfArithmeticSlices(vector& nums) {

m_c = nums.size();

vector<std::unordered_map> dp(m_c);

int iRet = 0;

for (int i = 0; i < m_c; i++)

{

for (int j = 0; j < i; j++)

{

long long tmp = 1LL * nums[i] – nums[j];

auto it = dp[j].find(tmp);

int iNum = (dp[j].end() == it) ? 0 : it->second ;

iRet += iNum;

dp[i][tmp] += iNum + 1;

}

}

return iRet;

}

int m_c;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 **C+

+17**

如无特殊说明，本算法用**C++**实现。