动态规划

动态规划

动态规划(Dynamic Programming,简称 DP)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的算法思想。

基本概念

核心思想

  1. 最优子结构:问题的最优解包含子问题的最优解
  2. 重叠子问题:子问题会重复出现,可以保存子问题的解
  3. 无后效性:某阶段的状态确定后,后续状态的演变不再受此前各状态及决策的影响

解题步骤

  1. 确定状态和选择
  2. 明确 dp 数组的定义
  3. 找出状态转移方程
  4. 确定初始条件和边界情况
  5. 确定遍历顺序

常见类型

线性 DP

  1. 单序列问题

    • 最长上升子序列
    • 最大子数组和
    • 打家劫舍
  2. 双序列问题

    • 最长公共子序列
    • 编辑距离
    • 正则表达式匹配

区间 DP

  • 最长回文子序列
  • 戳气球
  • 矩阵链乘法

背包 DP

  1. 0-1背包
  2. 完全背包
  3. 多重背包
  4. 分组背包

状态压缩 DP

  • 旅行商问题
  • 集合划分问题
  • 状态表示与压缩

树形 DP

  • 树的最大独立集
  • 树的最小支配集
  • 树的直径

数位 DP

  • 数字计数
  • 数字染色
  • 数字游戏

优化技巧

空间优化

  1. 滚动数组
  2. 状态压缩
  3. 一维化处理

时间优化

  1. 预处理
  2. 单调队列/单调栈
  3. 四边形不等式

解题技巧

状态设计

  1. 考虑问题的最后一步
  2. 化整为零,分解问题
  3. 寻找状态表示方式

方程推导

  1. 考虑所有可能的转移
  2. 确保转移的完备性
  3. 验证转移的正确性

边界处理

  1. 初始状态的设定
  2. 特殊情况的处理
  3. 数组越界的预防

常见误区

  1. 贪心与动态规划的混淆
  2. 递归与动态规划的区别
  3. 状态设计过于复杂
  4. 遗漏重要状态转移

练习建议

  1. 从简单问题开始
  2. 多画状态转移图
  3. 注重空间时间优化
  4. 总结相似问题规律

复杂度分析

时间复杂度

  • 由状态数量和状态转移决定
  • 通常为
  • 状态压缩可能达到

空间复杂度

  • 基本为
  • 可通过滚动数组优化
  • 某些问题可降至
牛客代码笔记-牛栋 文章被收录于专栏

汗牛充栋,学海无涯。<br/> 内含算法知识点讲解,以及牛客题库精选例题。<br/> 学习算法,从牛栋开始。

全部评论

相关推荐

避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
这一集&nbsp;硕士输的很惨
找工作ing10:就是这样不是硕士不愿意脱下长衫,是人家觉得屈才了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务