动态规划和贪心法的区别( 五 )
■网友
什么时候贪心法得到的是全局最优解呢？你也知道，贪心法因为只是每一步取区部最优，得到的不一定是全局最优解。那么究竟一个贪心策略是不是全局最优解，这是需要证明的。证明的套路多种多样，常见的方案就是说对于任何其他方案，我贪出来的都不比你差，那么我贪的就是就是最优解了。一类问题可以用拟阵来证明。另外也可以将问题规约到已知的贪心问题上。比赛时也可以使用野路子：写一个数据生成器，一个暴力程序，然后枚举思路，如果枚举的解一直等于暴力的解，那么问题就不大了。基本上是不同的两种东西。除非动态规划决策的每一步都是有规律可循的，就可以转化成贪心法求解了。
■网友
泻药，举个例子吧！
动态规划 贪心算法中都有背包问题，dp中的背包问题通常是01背包问题，贪心中的背包问题通常是比较简单的。
动态规划中的背包问题通常是选择或者不选择，选择是1不选就是0，而且相比贪心，你的东西是不可分的！！！不可分的！！！
贪心问题中的背包你通常会发现你所选取的物品可能不是一个完整的，其实简单来说就是你按照某种顺序（比如单价最高，或者性价比最高）其实就是按照单位数量内的性价比取东西，升序或者降序来选取！
■网友
对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。来源：百度百科
■网友
个人理解回溯算法，动态规划和贪心算法其实是循序渐进的。回溯算法即是暴力的枚举，每一步对所有可能都进行计算，计算到达终点即返回，每一步返回后都要把状态回归到之前的状态。回溯算法的痛点是他有很多重复的计算，解决的办法是引入备忘录，备忘录记录了每一步的结果，这其实就是子问题的最优解，动态规划由此产生。所以使用动态规划时必须要满足无后效性，子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。如果一个问题没有重叠子问题，那就只能使用回溯算法，比如N皇后问题。
【动态规划和贪心法的区别】 对于有些问题，我们通过建立数学模型之后明确知道了子问题的最优解，那么就不需要枚举各种情况了。比如有 5 元，2 元和 1 元三种硬币无限个，求用这些硬币兑换 x 元的最少硬币个数。解决这个问题总是先考虑最大面额的硬币，并不需要枚举。但是对于 5 元，4 元和 1 元这三个面额，贪心算法并不能得出最优解。
推荐阅读
![[博智客]为何独缺美国？俄罗斯：必须中国点头，全球60国请求加入“组织”](https://imgcdn.toutiaoyule.com/20200421/20200421113904382858a_t.jpeg)
- 在路上|在路上开廉价车和豪车的区别，看看网友的真实体会
- 啥是微信开发WEB前端
- Java工程师和C++工程师在工作上有啥区别哪个更适合自身发展
- 软件产品与传统商品、软件行业与传统行业的区别是啥
- |有种粗心叫“错把喉癌当成咽喉炎”，医生通俗告诉你两者区别在哪
- 动态规划能得到一类问题的最优解，比如背包问题用动态规划来解决，怎样证明这个解就是相对应问题的最优解呢
- Python3.4和3.5区别大么
- 计科，通信工程，电子信息工程这三个专业有啥区别
- 电子班牌和智能班牌有啥区别
- 类似于「创意周末」、「懒人周末」、「周末去哪儿」这类城市生活应用有啥区别