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

这篇具有很好参考价值的文章主要介绍了【动态规划】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
-231 <= nums[i] <= 231 - 1

动态规划

时间复杂度😮(nn)
空间复杂度😮(nn)

变量解析

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

mSubCount1 mSubCount1[i][sub]表示以nums[i]结尾,差为sub的“准等差”数量。
mSubCount2 mSubCount2[i][sub]表示以nums[i]结尾,差为sub的等差数列的数量。

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

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

动态规划的状态表示 mSubCount1 和mSubCount2
动态规划的转移方程 mSubCount2 [i][sub] +=mSubCount1 [j][sub]+ mSubCount2 [j][sub] mSubCount1[i][sub]++
动态规划的初始状态
动态规划的填表顺序 i和j都是从小到大处理,确保动态规划的无后效性
动态规划的返回值 Sumi,submSubCount2[i][sub]

代码

核心代码

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);
	}


}

可以优化掉一个变量

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;
};

【动态规划】C++算法:446等差数列划分 II - 子序列,# 算法题,算法,动态规划,c++,leetcode,子序列,等差数列,数量

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。

【动态规划】C++算法:446等差数列划分 II - 子序列,# 算法题,算法,动态规划,c++,leetcode,子序列,等差数列,数量文章来源地址https://www.toymoban.com/news/detail-778939.html

到了这里,关于【动态规划】C++算法:446等差数列划分 II - 子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C语言蓝桥杯每日一题】——等差数列

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2023年04月09日
    浏览(78)
  • 华为OD机试真题 Java 实现【等差数列】【2023 B卷 100分】,附详细解题思路

    本专栏收录于《华为OD机试(JAVA)真题(A卷+B卷)》。 刷的越多,抽中的概率越大 ,每一题都有详细的答题思路、详细的代码注释、样例测试,订阅后,专栏内的文章都可看,可加入华为OD刷题群(私信即可),发现新题目,随时更新,全天CSDN在线答疑。 专栏福利 :限时订

    2024年02月16日
    浏览(60)
  • 蓝桥杯专题-真题版含答案-【九宫幻方】【打鱼还是晒网】【阶乘尾数零的个数】【等差素数列】

    点击跳转专栏=Unity3D特效百例 点击跳转专栏=案例项目实战源码 点击跳转专栏=游戏脚本-辅助自动化 点击跳转专栏=Android控件全解手册 点击跳转专栏=Scratch编程案例 点击跳转=软考全系列 点击跳转=蓝桥系列 专注于 Android/Unity 和各种游戏开发技巧,以及 各种资源分享 (网站、

    2024年02月15日
    浏览(41)
  • C++算法 —— 动态规划(1)斐波那契数列模型

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月10日
    浏览(44)
  • 【算法学习】斐波那契数列模型-动态规划

            我在算法学习过程中,针对斐波那契数列模型的动态规划的例题进行了一个整理,并且根据标准且可靠一点的动态规划解题思路进行求解类似的动归问题,来达到学习和今后复习的必要。         所谓的斐波那契数列模型,即当前状态的值等于前两种状态的值之和。

    2024年02月04日
    浏览(54)
  • 【算法优选】 动态规划之斐波那契数列模型

    动态规划相关题目都可以参考以下五个步骤进行解答: 状态表⽰ 状态转移⽅程 初始化 填表顺序 返回值 后面题的解答思路也将按照这五个步骤进行讲解。 泰波那契序列 Tn 定义如下: T0 = 0, T1 = 1, T2 = 1, 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n,请返回第 n 个泰波那契

    2024年02月05日
    浏览(55)
  • 动态规划入门:斐波那契数列模型以及多状态(C++)

        动态规划(Dynamic programming,简称 DP)是一种解决多阶段决策问题的算法思想。它将问题分解为多个阶段,并通过保存中间结果来避免重复计算,从而提高效率。 动态规划的解题步骤一般分为以下几步: 思考状态表示,创建dp表(重点) 分析出状态转移方程(重点) 初始化 确定

    2024年02月11日
    浏览(42)
  • Java数据结构与算法:动态规划之斐波那契数列

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编。在这寒冷的季节里,让我们一同探讨Java中的动态规划,重点关注解决问题的经典代表之一——斐波那契数列。 动态规划简介 动态规划是一种解决问题的数学方法,通常用于优化递归算法。它通过将问

    2024年01月22日
    浏览(47)
  • P1025 [NOIP2001 提高组] 数的划分———C++(动态规划、DFS)

    将整数 n n n 分成 k k k 份,且每份不能为空,任意两个方案不相同(不考虑顺序)。 例如: n = 7 n=7 n = 7 , k = 3 k=3 k = 3 ,下面三种分法被认为是相同的。 1 , 1 , 5 1,1,5 1 , 1 , 5 ; 1 , 5 , 1 1,5,1 1 , 5 , 1 ; 5 , 1 , 1 5,1,1 5 , 1 , 1 . 问有多少种不同的分法。 n , k n,k n , k ( 6 n ≤ 200 6n le

    2024年01月22日
    浏览(36)
  • 算法题——华为OD机试——整数划分排序/员工分月饼——动态规划——Java

    一个考察动态规划的机试题的数学模型建立,和两种思路的取舍 公司分月饼,m个员工,买了n个月饼,m = n,每个员工至少分一个月饼,但是也可以分到多个,单人分到最多月饼的个数是Max1,单人分到第二多月饼个数是Max2。 但需要满足Max1-Max2 = 3,单人分到第n-1多月饼个数是

    2024年03月16日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包