1. 寻找最优子结构
2. 证明分隔的剩下部分（通常是2个部分）也能满足最优子结构
3. 设计动态规划方程式，函数
4. 证明方法正确性
5. 迭代计算得出结果
算法中最直观的是自顶向下迭代，但是这样会形成一个2^n次方的时间复杂度的算法，可以使用备忘录和自底向上递归来实现。
通常最优子结构将整个问题分解为2部分，2部分中每部分都有最优子结构，依次迭代产生最终结果。
个人理解：贪心（贪婪）算法是动态规划算法的一种特殊算法。
1.寻找寻找最优子结构
2.设计递归算法
3.证明我们做出的是一个贪心选择，只剩下一个子问题（和动态规划的最大区别）
4.证明贪心选择总是安全的
5.递归，实现算法
最大的区别在于做出贪心选择,贪心选择之后，只剩下一个子问题。这样我们可以设计出时间复杂度O（N）的算法。
--tags: 算法，动态规划 动态规划解题 引入：动态规划 和贪心法 都是算法的思想方法 贪心算法——像 第一类...
解法 动态规划解法 贪心算法
动态规划和贪心算法的相同点和不同点 相同点：动态规划和贪心算法的都是一种递推算法，都是由局部最优解来推导全局最优解...
动态规划 参考：算法分析与设计-贪心&动归 漫画：什么是动态规划？ 【数据结构与算法】 DP 动态规划 介绍 介绍...
动态规划和贪心算法都是用来求最优化问题，且二者都必须具有最有子结构。贪心算法可以解决的问题，动态规划都能解决，可以...
动态规划 动态规划设计思路： 算法实现 通常最优子结构将整个问题分解为2部分，2部分中每部分都有最优子结构，依次迭...
Dynamic Programming（动态规划） Greedy（贪心算法） Complete Search（穷举...
[toc] 在《算法导论》中举了买股票和割铁棒的例子来说明动态规划和贪心算法的主体思想。 贪心算法：总是做出在当前...
0. 动态规划分析 0.1 动态规划、递归和贪心算法的区别 动态规划就是利用分治思想和解决冗余的办法来处理问题，所...
贪心算法 先来比较一下贪心算法和动态规划 贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择，不考虑整体，...
本文标题：动态规划和贪心算法笔记
本文链接：https://www.haomeiwen.com/subject/jcsxcftx.html
网友评论