作者推薦

視頻算法專題

本文涉及知識點(diǎn)

動態(tài)規(guī)劃匯總

446. 等差數(shù)列劃分 II - 子序列

給你一個(gè)整數(shù)數(shù)組 nums ，返回 nums 中所有 等差子序列 的數(shù)目。
如果一個(gè)序列中 至少有三個(gè)元素 ，并且任意兩個(gè)相鄰元素之差相同，則稱該序列為等差序列。
例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
再例如，[1, 1, 2, 5, 7] 不是等差序列。
數(shù)組中的子序列是從數(shù)組中刪除一些元素（也可能不刪除）得到的一個(gè)序列。
例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一個(gè)子序列。
題目數(shù)據(jù)保證答案是一個(gè) 32-bit 整數(shù)。
示例 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
解釋：數(shù)組中的任意子序列都是等差子序列。
參數(shù)范圍：
1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1

動態(tài)規(guī)劃

時(shí)間復(fù)雜度??(nn)
空間復(fù)雜度??(nn)

變量解析

長度大于2的稱為等差子序列，長度等于2的不妨稱為“準(zhǔn)等差”。

動態(tài)規(guī)劃的細(xì)節(jié)，方便檢查

兩層循環(huán)，分別枚舉等差數(shù)列的最后一個(gè)元素和倒數(shù)第二個(gè)元素。

代碼

核心代碼

class Solution {
public:
	int numberOfArithmeticSlices(vector<int>& nums) {
		m_c = nums.size();
		vector<unordered_map<long long, int>> 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<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& 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<int> 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);
	}


}

可以優(yōu)化掉一個(gè)變量

class Solution {
public:
int numberOfArithmeticSlices(vector& nums) {
m_c = nums.size();
vector<unordered_map<long long, int>> 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<long long, int>> 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;
};

擴(kuò)展閱讀

視頻課程

有效學(xué)習(xí)：明確的目標(biāo) 及時(shí)的反饋 拉伸區(qū)（難度合適），可以先學(xué)簡單的課程，請移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰(zhàn)斗了，為老板分憂，請學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176

相關(guān)下載

想高屋建瓴的學(xué)習(xí)算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653

測試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 **C+

+17**
如無特殊說明，本算法用**C++**實(shí)現(xiàn)。

文章來源地址http://www.zghlxwxcb.cn/news/detail-778939.html

到了這里，關(guān)于【動態(tài)規(guī)劃】C++算法：446等差數(shù)列劃分 II - 子序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！