最近在做USACO的training,又碰到了greedy algorithm的训练章节。回想起来大学时光学习dynamic programming的时候,一直搞不清,后来看Introduction to Algorithm,突然顿悟,那种感觉真的是很爽,我觉得一直学不明白,有一天突然顿悟的感觉,大家都应该去体验一下,真的很爽。
greedy的思想太简单了,每次都找最优的,也就是每次的结果只有一个点咯。不过应用greedy algorithm的时候需要特别注意条件,局部最优即全局最优。这是多于dynamic programming的一点。
然后dynamic programming吧,它和greedy的不同是什么?没有局部最后即全局最优的这种优势,但这次的状态是基于前一状态的,那么前一状态是什么呢?不好意思我不知道。不知道怎么办,列出前一状态的所有状态,前一状态有哪些?还是不知道,那怎么办呢,从第一个阶段的状态开始记录,然后基于第一状态算出第二状态的最优,那么全局最优一定存在于这些局部最优的一个路线中。所以dp每次记录的是一系列状态,而不是像greedy只记录当前的最优解这一个状态。
所以才有了所谓的打表,理解了这一个过程,就理解了dp后续所有的优化。
相关推荐
动态规划和贪心算法的区别 贪心算法和动态规划.pdf
贪心算法、分治算法和动态规划的区别 贪心算法和动态规划.pdf
活动安排问题的动态规划、贪心算法和树搜索算法求解。 比如有一个多媒体教室,现在有四个待举办活动A、B、C、D。A是在8:00到10:00举行,简单记为[8, 10];B是[12, 14];C是[15, 17];D是[11, 19]。为了让尽可能多的...
会议安排(贪心算法和动态规划) 贪心算法和动态规划.pdf
动态规划和贪心算法区别,供大家学习,如有毛病,还大神望误喷。
动态规划,贪心算法,webservice,xml解析
贪心算法和动态规划以及分治法的区别? (1) 贪心算法和动态规划.pdf
【数据结构】贪心算法和动态规划 贪心算法和动态规划.pdf
贪心算法和动态规划的区别与联系 贪心算法和动态规划.pdf
贪心算法和动态规划(Java实现) 贪心算法和动态规划.pdf
网上搜的贪心算法和动态规划算法课件,主要分析了这两类算法的解法。包括:程序员代码面试指南-第四章递归和动态规划[牛客试网试读版],7.贪心法和动态规划。
贪心算法和动态规划以及分治法的区别? 贪心算法和动态规划.pdf
记录一道面试算法题餐馆问题(贪心和动态规划) 贪心算法和动态规划.pdf
动态规划算法-多边形游戏。回溯法-符号三角形问题。贪心算法-计算加油次数。包括流程图+代码+实验结果截屏+实验总结。
有关动态规划和贪心的算法,新手可以看看!我是新手!
算法分析与设计实验-基于Vue3和Typescript实现的排序、动态规划、贪心算法、检索源码.zip算法分析与设计实验-基于Vue3和Typescript实现的排序、动态规划、贪心算法、检索源码.zip算法分析与设计实验-基于Vue3和...
动态规划算法和贪心算法,这两种算法的的比较与分析
ES6的JavaScript算法思想实现之分而治之,动态规划,贪心算法和回溯算法 贪心算法和动态规划.pdf
动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法
主要针对贪心算法原理及实现和在动态规划中的应用