首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐
2025年5月19日 星期一 9:31pm

动态规划的时间复杂度优化

  • 25-02-22 08:41
  • 2284
  • 7516
blog.csdn.net

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

优化动态规划的时间复杂度,主要有如下几种:

一,不同的状态表示。

比如:n个人,m顶帽子。
第一种方式:dp[i][mask] ,i表示前i个人已经选择帽子,mask 表示 那些帽子已经选择。 空间复杂度:O(n2m)。
第二种方式:dp[i][mask] ,i表示前i个帽子已经选择,mask表示那些人已经选择。 空间复杂度:O(m22)。
n大,则现在方式一;否则选择方式二。

【状态压缩】【动态规划】【C++算法】1125.最小的必要团队

二,通过优化状态减少状态数

例一

【动态规划】【C++算法】2518. 好分区的数目
num的长度 ∈ \in ∈[1,1000],num[i] ∈ \in ∈[0,106] k ∈ \in ∈[0,1000]。
将num的元素放到两个数组中,两个数组的和都为k。
由于num[i] >=0,所以 数组和已经大于k 的无论如何都不会等于k,抛弃。
dp[k1][k2] 的状态数是固定。
当处理完 n u m [ 0 , i ) 时 , 两个数组的和是固定    ⟺    k 1 + k 2 ≡ ∑ j : 0 i − 1 n u m s [ j ] 当处理完num[0,i)时,两个数组的和是固定 \iff k1+k2 \equiv \sum\Large_{j:0}^{i-1} nums[j] 当处理完num[0,i)时,两个数组的和是固定⟺k1+k2≡∑j:0i−1​nums[j]
我记录k1或k2就可以了。新问题是k1 可能是5e8。
{ k 1 k 1 < k − m i n ( k 2 , k ) e l s e {k1k1<k−min(k2,k)else

{k1−min(k2,k)k1<kelse
{k1−min(k2,k)​k1<kelse​

例子二

2742. 给墙壁刷油漆
付费工人,各任务用时time[i],免费工人用时1,time.length ∈ \in ∈[1,500]。付费工人用时和必须大于等于免费工人用时。如果分别记录付费工人和免费工人用时,则状态数:500*500。
付费工人用时和必须大于等于免费工人    ⟺    \iff ⟺ (statu = 付费工人用时 - 免费工人用时) >= 0
statu ∈ \in ∈ [-500,500] 可以记录状态的时候+500,解析状态的时候再-500。

三 通过优化转移方程

转移方程主要有两种:
a,枚举前置状态,更新后置状态。除剪枝小幅提升性能外,暂时没发现优化方法。
b,枚举后置状态,通过前置状态计算后置状态。利用前缀和、极值、优先队列(堆)、单调栈(队列、向量)、预处理 等优化。

2617 网格图中最少访问的格子数两种方法:分别用单调栈、优先队列优化
【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组前缀和
【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II枝小幅提升性能
【动态规划】【C++算法】1563 石子游戏 V极值

四 匹配无限次可以拆分成匹配0次和1次

以通配符为例。
abc 匹配 *
初始匹配长度0
处理* :
长度0的后置状态:*不匹配任何字符,匹配长度0。
长度0的后置状态:*匹配一个字符,匹配长度1。
长度1的后置状态:*不匹配任何字符,匹配长度1。
长度1的后置状态:*匹配一个字符,匹配长度2。
⋮ \quad \quad \vdots ⋮
总计: *可以匹配0到无限字符,才可以这样处理。 .只能匹配一个字符不能这样处理。

【动态规划】【字符串】C++算法:正则表达式匹配

【状态压缩】【动态规划】【C++算法】691贴纸拼词
【动态规划】【数学】【C++算法】1449. 数位成本和为目标值的最大数字
【动态规划】【C++算法】2188. 完成比赛的最少时间

五 逆向思考

【动态规划】【 矩阵】【逆向思考】C++算法174地下城游戏
正向思考:要记录进入(r,c)后的健康,还有记录初始健康。比如:路径一: 3 → \rightarrow → -2 ,初始只需要1,最终健康2。
路径二: -1 → \rightarrow → 4 ,初始要求 2,最终健康度 5。如果终点格是-1,前者能过。 如果是-4,后者能过。前者需要4,才能过。
{ 路径一初始 1 ,路径二初始 2 终点 < − 1 路径一初始 4 ,路径二初始 2 终点 − 4 {路径一初始1,路径二初始2终点<−1路径一初始4,路径二初始2终点−4

{路径一初始1,路径二初始2路径一初始4,路径二初始2​终点<−1终点−4​

【动态规划】【C++算法】741摘樱桃

六 去掉重复

【动态规划】C++算法:403.青蛙过河

扩展阅读

视频课程

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

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览58433 人正在系统学习中
群中有博文配套源码
QQ群名片
注:本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/136019609"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2024 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top