从零开始学习贪心算法
时间: 2023-09-22 09:09:12 浏览: 292
从零开始学习贪心算法需要掌握以下几个点:
1. 贪心算法的定义:贪心算法是指在问题求解过程中,总是做出当前看来最好的选择,而不考虑整体最优解。贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
2. 贪心算法的解题步骤:建立数学模型描述问题,将问题分解为若干个子问题,对每个子问题求解得到局部最优解,将局部最优解合成原问题的最优解。
3. 贪心算法与动态规划的关系:贪心算法是动态规划的一种特例。贪心算法不需要知道一个节点所有子树的情况,只需要选择当前问题的最优解路径,一直走到底即可。而动态规划需要自底向上构造子问题的解。
4. 活动选择问题是贪心算法的一个经典例子。在活动选择问题中,需要在同一天使用同一个教室举行多个活动,要求选择尽可能多的活动不冲突地进行。
综上所述,从零开始学习贪心算法,要理解贪心算法的定义和特点,掌握贪心算法的解题步骤,了解贪心算法与动态规划的关系,并通过经典例子如活动选择问题来实践和加深对贪心算法的理解。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [从0开始学贪心算法](https://blog.csdn.net/weixin_45024585/article/details/107515191)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *2* [leetcode338-leetcode:从零开始](https://download.csdn.net/download/weixin_38750644/19950444)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *3* [从零开始学贪心算法](https://blog.csdn.net/qq_32400847/article/details/51336300)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 33.333333333333336%"]
[ .reference_list ]