很奇怪，动态规划和贪心算法也有很多相似之处：
相同点：
0，两者都用于求解最优化问题
1，两者都将待求解的问题分解成若干子问题
2，两者都需要确定最优子结构，才能决定是否可以使用该方法
3，两者都需要构造递归式
最优子结构：一个问题的最优解包含其子问题的最优解
不同点：
1，动态规划是自底向上计算，类似于将问题的规模从1开始，计算到n,其中i的求解依赖于i-1的结果；贪心算法则是自顶向下计算，选择当前一个最优解，然后再看剩余问题的最优解，一路剥削下去
2，动态规划比贪心算法更加细致精确，贪心算法有时候求不出最优解
贪心算法：面对规模为n的问题，每次选择当前情况的一个最优解，然后在看剩余的n-1规模的问题。
贪心原则：最能符合问题需求的选择
贪心算法需要论证
每次贪心选择的解组合在一起就是最优解 这个结论是否正确
动态规划 参考：算法分析与设计-贪心&动归 漫画：什么是动态规划？ 【数据结构与算法】 DP 动态规划 介绍 介绍...
--tags: 算法，动态规划 动态规划解题 引入：动态规划 和贪心法 都是算法的思想方法 贪心算法——像 第一类...
解法 动态规划解法 贪心算法
目录 算法基础 算法复杂性 递归与分治 回溯法与分支限界法 贪心算法 动态规划法 NP问题 概率算法 现代优化算法...
Dynamic Programming（动态规划） Greedy（贪心算法） Complete Search（穷举...
链接：很特别的一个动态规划入门教程动态规划与贪心算法的区别与联系 那么遇到问题如何用动态规划去解决呢？根据上面的分...
动态规划和贪心算法都是用来求最优化问题，且二者都必须具有最有子结构。贪心算法可以解决的问题，动态规划都能解决，可以...
动态规划和贪心算法的相同点和不同点 相同点：动态规划和贪心算法的都是一种递推算法，都是由局部最优解来推导全局最优解...
目录： 算法简介 排序算法 递归与穷举 贪心与分治 动态规划和回溯 1.算法简介 解题方案的准确而完整的描述，是一...
八皇后 A *寻路 背包问题（动态规划方法） 背包问题（贪心算法）
本文标题：动态规划与贪心算法
本文链接：https://www.haomeiwen.com/subject/edsgqttx.html
网友评论