跳至主要內容

3.5 贪心算法


3.5 贪心算法

什么是贪心算法?

贪心算法,又称贪婪算法,在对问题求解时,总是做出在当前看来最好的选择,期望通过每个阶段的局部最优选择达到全局最优,但结果不一定最优。

适用场景

简单的说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解,就能用贪心算法的到最后的最优解,这种子问题最优解称为最优子结构。

贪心算法与动态规划的区别

贪心算法与动态规划的不同点在于它对每个子问题的解决方案都做出当前的最优选择,不能回退,而动态规划会保留之前的运算结果,并根据之前的结果进行选择,有回退的功能,贪心是动态规划的理想化的情况。

相关题目

题号标题题解标签难度
455分发饼干open in new window贪心 数组 双指针 1+
860柠檬水找零open in new window贪心 数组
56合并区间open in new window[✓]数组 排序
435无重叠区间open in new window贪心 数组 动态规划 1+
452用最少数量的箭引爆气球open in new window[✓]贪心 数组 排序
55跳跃游戏open in new window[✓]贪心 数组 动态规划
45跳跃游戏 IIopen in new window[✓]贪心 数组 动态规划
392判断子序列open in new window[✓]双指针 字符串 动态规划
122买卖股票的最佳时机 IIopen in new window[✓]贪心 数组 动态规划
561数组拆分open in new window贪心 数组 计数排序 1+
1710卡车上的最大单元数open in new window贪心 数组 排序
1217玩筹码open in new window贪心 数组 数学
1247交换字符使得字符串相同open in new window贪心 数学 字符串
1400构造 K 个回文字符串open in new window贪心 哈希表 字符串 1+
921使括号有效的最少添加open in new window[✓] 贪心 字符串
1029两地调度open in new window贪心 数组 排序
1605给定行和列的和求可行矩阵open in new window贪心 数组 矩阵
135分发糖果open in new window[✓]贪心 数组
134加油站open in new window[✓]贪心 数组
53最大子数组和open in new window[✓]数组 分治 动态规划
376摆动序列open in new window贪心 数组 动态规划
738单调递增的数字open in new window贪心 数学
402移掉 K 位数字open in new window 贪心 字符串 1+
861翻转矩阵后的得分open in new window贪心 位运算 数组 1+
670最大交换open in new window[✓]贪心 数学