【动态规划总结(三)】比较

这一章我们将会介绍分治和贪心算法的核心思想,并与动态规划算法进行比较。

分治

解决分治问题的时候,思路就是想办法把问题的规模减小,有时候减小一个,有时候减小一半,然后将每个小问题的解以及当前的情况组合起来得出最终的结果。
例如归并排序和快速排序,归并排序将要排序的数组平均地分成两半,快速排序将数组随机地分成两半。
然后不断地对它们递归地进行处理。
这里存在有最优的子结构,即原数组的排序结果是在子数组排序的结果上组合出来的,但是不存在重复子问题,因为不断地对待排序的数组进行对半分的时候,两半边的数据并不重叠,分别解决左半边和右半边的两个子问题的时候,

没有子问题重复出现,这是动态规划和分治的区别。

贪心

  1. 关于最优子结构
    贪心:每一步的最优解一定包含上一步的最优解,上一步之前的最优解无需记录
    动态规划:全局最优解中一定包含某个局部最优解,但不一定包含上一步的局部最优解,因此需要记录之前的所有的局部最优解

  2. 关于子问题最优解组合成原问题最优解的组合方式
    贪心:如果把所有的子问题看成一棵树的话,贪心从根出发,每次向下遍历最优子树即可,这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况,于是构不成一棵完整的树
    动态规划:动态规划需要对每一个子树求最优解,直至下面的每一个叶子的值,最后得到一棵完整的树,在所有子树都得到最优解后,将他们组合成答案

  3. 结果正确性
    贪心不能保证求得的最后解是最佳的,复杂度低
    动态规划本质是穷举法,可以保证结果是最佳的,复杂度高

- 分治算法 动态规划算法 贪心算法
适用类型 通用 优化 优化
子问题 每个都不相同 有很多重复 只有一个
最优子结构 没有要求 必须满足 必须满足
子问题数 全部都要解 全部都要解 只解一个
全部评论

相关推荐

Tom哥981:让我来压力你!!!: 这份简历看着“技术词堆得满”,实则是“虚胖没干货”,槽点一抓一大把: 1. **项目描述是“技术名词报菜名”,没半分自己的实际价值** 不管是IntelliDoc还是人人探店,全是堆Redis、Elasticsearch、RAG这些时髦词,但你到底干了啥?“基于Redis Bitmap管理分片”是你写了核心逻辑还是只调用了API?“QPS提升至1500”是你独立压测优化的,还是团队成果你蹭着写?全程没“我负责XX模块”“解决了XX具体问题”,纯把技术文档里的术语扒下来凑字数,看着像“知道名词但没实际动手”的实习生抄的。 2. **短项目塞满超纲技术点,可信度直接***** IntelliDoc就干了5个月,又是RAG又是大模型流式响应又是RBAC权限,这堆活儿正经团队分工干都得小半年,你一个后端开发5个月能吃透这么多?明显是把能想到的技术全往里面塞,生怕别人知道你实际只做了个文件上传——这种“技术堆砌式造假”,面试官一眼就能看出水分。 3. **技能栏是“模糊词混子集合”,没半点硬核度** “熟悉HashMap底层”“了解JVM内存模型”——“熟悉”是能手写扩容逻辑?“了解”是能排查GC问题?全是模棱两可的词,既没对应项目里的实践,也没体现深度,等于白写;项目里用了Elasticsearch的KNN检索,技能栏里提都没提具体掌握程度,明显是“用过但不懂”的硬凑。 4. **教育背景和自我评价全是“无效信息垃圾”** GPA前10%这么好的牌,只列“Java程序设计”这种基础课,分布式、微服务这些后端核心课提都不提,白瞎了专业优势;自我评价那堆“积极认真、细心负责”,是从招聘网站抄的模板吧?没有任何和项目挂钩的具体事例,比如“解决过XX bug”“优化过XX性能”,纯废话,看完等于没看。 总结:这简历是“技术名词缝合怪+自我感动式凑数”,看着像“背了后端技术栈名词的应届生”,实则没干货、没重点、没可信度——面试官扫30秒就会丢一边,因为连“你能干嘛”都没说清楚。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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