文章目录贪心的定义和思想贪心的要素贪心的优点和缺点目录贪心的定义和思想贪心是一种算法思想其含义是在求解过程中每一步总是做出当前的最优选择。贪心思想不考虑全局最优只考虑局部最优。贪心思想在之前已经有所涉及哈夫曼树的构建就是基于贪心的思想图算法中的单源最短路径和最小生成树也是基于贪心的思想。由于贪心思想为只考虑局部最优因此使用贪心策略得到的结果不一定是全局最优解。贪心问题的求解思路为将问题分解成多个子问题对于每个子问题得到局部最优解将子问题的局部最优解合成原始问题的解。贪心的要素贪心的要素有两点一是贪心选择性质二是最优子结构性质。贪心选择性质的含义是问题的全局最优解可以通过贪心选择达到每次贪心选择都得到局部最优解并将问题简化成规模更小的子问题。最优子结构性质的含义是问题的最优解包含子问题的最优解。只有当问题具备贪心的要素时才能使用贪心策略得到最优解。使用贪心策略时需要证明贪心策略可以得到全局最优解即问题具有贪心选择性质和最优子结构性质证明的思路是不使用贪心策略时不可能得到更优解。贪心的优点和缺点贪心的优点是实现较为简单且时间复杂度通常较低。当数据规模较大时使用贪心策略可以在较短的时间内得到答案。贪心的缺点是不能确保得到全局最优解当局部最优策略与全局最优策略不一致时使用贪心策略得到的解一般不是全局最优解。目录贪心题目和有限的最长子序列贪心题目非递增顺序的最小子序列贪心题目数组大小减半贪心题目玩筹码贪心题目种花问题贪心题目保持城市天际线贪心题目分割平衡字符串贪心题目卡车上的最大单元数贪心题目数组拆分贪心题目三角形的最大周长贪心题目K 次取反后最大化的数组和贪心题目柠檬水找零贪心题目分发饼干贪心题目运动员和训练师的最大匹配数贪心题目优势洗牌贪心题目递减元素使数组呈锯齿状贪心题目划分字母区间贪心题目交换字符使得字符串相同贪心题目令牌放置贪心题目两地调度贪心题目最少的后缀翻转次数贪心题目不含 AAA 或 BBB 的字符串贪心题目具有给定数值的最小字符串贪心题目十-二进制数的最少数目贪心题目坏了的计算器贪心题目得到目标值的最少行动次数贪心题目使绳子变成彩色的最短时间贪心题目所有排列中的最大和贪心题目翻转矩阵后的得分贪心题目字符频次唯一的最小删除次数贪心题目构造 K 个回文字符串贪心题目单调递增的数字贪心题目行相等的最少多米诺旋转贪心题目删除子字符串的最大得分贪心题目Dota2 参议院贪心题目救生艇贪心题目受标签影响的最大值贪心题目交换一次的先前排列贪心题目最多能完成排序的块贪心题目安排工作以达到最大收益贪心题目需要教语言的最少人数贪心题目给定行和列的和求可行矩阵贪心题目加油站贪心题目分发糖果贪心题目最大数贪心题目和为 K 的最少斐波那契数字数目贪心题目得到目标数组的最少函数调用次数贪心题目和为目标值且不重叠的非空子数组的最大数目贪心题目用最少数量的箭引爆气球贪心题目任务调度器贪心题目可以到达的最远建筑贪心题目吃苹果的最大数目贪心题目重构 2 行二进制矩阵贪心题目最长快乐字符串贪心题目无重叠区间贪心题目形成目标数组的子数组最少增加次数贪心题目青蛙过河 II贪心题目分割数组为连续子序列贪心题目排布二进制网格的最少交换次数贪心题目IPO贪心题目最小区间贪心题目最多可以参加的会议数目贪心题目最大的团队表现值贪心题目距离相等的条形码贪心题目重构字符串贪心题目避免洪水泛滥贪心题目最多能完成排序的块 II贪心题目修改后的最大二进制字符串贪心题目按要求补齐数组贪心题目超级洗衣机贪心题目设置交集大小至少为 2贪心题目雇佣 K 名工人的最低成本贪心题目完成所有任务的最少初始能量贪心题目完成所有交易的初始最少钱数贪心题目翻转子数组得到最大的数组值贪心题目让数组不相等的最小总代价贪心题目强密码检验器
