算法合集之《浅谈贪心思想在动态规划中的应用》

贪心算法在优化问题中的运用贪心算法（Greedy Algorithm）是一种常用的算法思想，它在解决一些优化问题时具有很高的效率和实用性。

贪心算法的核心思想是每一步都选择当前状态下最优的解决方案，以期望最终能够得到全局最优解。

在实际应用中，贪心算法常常被用来解决一些最优化问题，如最短路径问题、背包问题、任务调度等。

本文将介绍贪心算法在优化问题中的运用，并通过具体案例来说明其应用场景和解决方法。

一、贪心算法的基本原理贪心算法是一种在每一步选择当前状态下最优解决方案的算法思想。

它与动态规划不同，贪心算法并不会保存之前的计算结果，而是根据当前状态做出最优选择。

贪心算法的优势在于简单、高效，适用于一些特定类型的问题。

贪心算法的基本原理可以总结为以下几点：1. 每一步都选择当前状态下的最优解决方案；2. 不考虑未来的结果，只关注当前状态的最优选择；3. 最终期望通过每一步的最优选择达到全局最优解。

二、贪心算法在优化问题中的应用1. 最短路径问题最短路径问题是图论中的经典问题，贪心算法可以用来解决一些简单的最短路径问题。

例如，在无权图中，从起点到终点的最短路径可以通过贪心算法来求解，每次选择距离最近的节点作为下一步的目标节点，直到到达终点为止。

2. 背包问题背包问题是一个经典的优化问题，贪心算法可以用来解决一些特定类型的背包问题。

例如，在分数背包问题中，每种物品可以取任意比例，贪心算法可以按照单位价值最高的顺序选择物品放入背包，直到背包装满为止。

3. 任务调度问题任务调度问题是一个常见的优化问题，贪心算法可以用来解决一些简单的任务调度问题。

例如，在单处理器任务调度中，每个任务有一个开始时间和结束时间，贪心算法可以按照结束时间的先后顺序对任务进行调度，以最大化处理器的利用率。

三、案例分析：活动选择问题活动选择问题是一个经典的优化问题，通过贪心算法可以高效地解决。

问题描述如下：假设有n个活动，每个活动都有一个开始时间和结束时间，活动之间不能交叉进行，问如何安排活动才能使参加的活动数量最多。

基于贪心算法的动态规划问题研究摘要：贪心算法的基本思想是将待求解问题时，总是进行局部最优选择，下一步的结果都是从上一步的结果推导出来的，且不可取消。

值得注意的是，贪心算法做出的仅仅是某种意义上的局部最优解，并不一定对所有问题都能得到整体最优解，但是对一些问题能够产生整体最优解或整体最优解的近似解。

本文对贪心思想在动态规划中的必要性和可行性进行分析，并利用贪心算法对背包问题进行深入研究。

关键词：动态规划 贪心算法 背包问题 最优解二 贪心思想运用到动态规划中的必要性和可行性动态规划的原理是：在求解问题的过程中，通过处理位于当前位置和所达目标之间的中间点来找到整个问题的解。

整个过程是递归的，每到一个新的中间点都是已访问过的点的一个函数。

适合于动态规划法的标准问题必须具有下列特点：1、整个问题的求解可以划分为若干个阶段的一系列决策过程。

2、每个阶段有若干可能状态。

3、一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。

4、在任一个阶段，最佳的决策序列和该阶段以后的决策无关。

5、各阶段状态之间的转换有明确定义的费用 在实际的动态规划的解题中，面临着两大困难：一是不知道题目是否可以用动态规划求解；二是即使能够想到用动态规划来求解，但因种种因素，算法的效率并不好。

那么使用贪心思想分析问题，但是对一些问题能够产生整体最优解或整体最优解的近似解。

三 贪心算法要素（1）贪心选择性质 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来实现。

对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。

（2）最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

四 背包问题描述给定n 种物品和一个背包，物品i 的重量为i w ，其价值为i v ，背包的容量为c ，问应如何选择装入背包中的物品，使得装入背包中的物品的总价值最大？对物品i 来说，可以全部装入背包，或部分装入背包。

关于贪⼼算法的经典问题（算法效率or动态规划）如题，贪⼼算法⾪属于提⾼算法效率的⽅法，也常与动态规划的思路相挂钩或⼀同出现。

下⾯介绍⼏个经典贪⼼问题。

（参考⾃刘汝佳著《算法竞赛⼊门经典》）。

P.S.下⽂皆是我⼀个字⼀个字敲出来的，绝对“童叟⽆欺”，哈哈。

(。

⌒∇⌒) 耗费了我的很多时间，所以——希望对⼤家有帮助啊~ (=^‸^=)⼀、背包相关问题1.最优装载问题：给出N个物体，有⼀定重量。

请选择尽量多的物体，使总重量不超过C。

解法：只关⼼数量多，便把重量从⼩到⼤排序，依次选，直到装不下。

2.部分背包问题：给出N个物体，有⼀定重量和价值。

请选择⼀些物体的⼀部分使在总重量不超过C的条件下总价值最⼤。

解法：关⼼总价值⼤，物体可取部分，便优先取单位重量价值较⼤的物体。

3.乘船问题：有N个⼈，有⼀定重量。

每艘船的最⼤载重量均为C，且最多载2⼈。

请⽤最少的船装载所有⼈。

解法：关⼼数量少，要尽量使每艘船的实际载重量尽量接近于最⼤载重量。

便把重量从⼩到⼤排序，每艘船依次先载⼀个⼈，再载重量最接近船的剩余可载重量的⼈。

这样可以使眼前的消费（剩余载重量）最少。

实现：⽤2个变量 l , r 分别从两头往中间移动，l 和 r 可共乘⼀艘船，或 r ⾃⼰乘⼀艘船。

⼆、区间相关问题1.选择不相交区间：数轴上有N个开区间(Li,Ri)，请选择尽量多个区间，并保证这些区间两两没有公共点。

解法：先把这些区间按找 Ri 从⼩到⼤的顺序排序，再对按序排列的每2个区间A,B分情况讨论：(1)A被B包含，选A最优；(2)A右边的⼀部分与B左边的⼀部分相交，选A最优，因为选A⽐B减少了与后⾯区间相交的可能性；(3)A、B不相交，便2个都选。

总的来说就是排序后，从左到右选第⼀个没有与前⾯已选的区间相交的区间。

O(n)。

拓展：那么如果可以⼀共覆盖两次，那该怎么选？ ——也就是。

2.区间选点问题：数轴上有N个闭区间[Li,Ri]，请选择尽量少的点，使得每个区间内都⾄少有⼀个点。

贪⼼算法与动态规划接下来学习贪⼼算法和动态规划，学习的过程中由于看的是录播，发现⽼师上课发现⼈有些没来有些许失落，下次在没有确定有充⾜时间的情况下，取消⼀切⽹络课程的报名。

贪⼼算法贪⼼算法在求解某个问题时，总是做出眼前的最⼤利益，也就是说只顾眼前不顾⼤局，所以他是局部最优解。

贪⼼算法不是对所有问题都能得到整体最好的解决办法，关键是贪⼼策略的选择，选择的贪⼼策略必须具备⽆后效性，即某个状态以前的状态不会影响以后的状态，只与当前状态有关。

贪⼼算法两个重要的特点是：（1）贪⼼策略（2）通过局部最优解能够得到全局最优解会议安排问题有N个同等级的会议需要在同⼀天使⽤同⼀个会议室，现在给出这N个会议的开始时间和结束时间，怎么样才能使会议室最⼤利⽤，安排最多场次的会议？分析：这个问题需要⽤到贪⼼算法，即先将这些会议根据结束时间⾃然排序，肯定是先安排最先结束的，如果最先安排最后结束的，那如果⼀个会议开的很久，那本来可以多安排⼏场结果全被这个占了，显然不是最优的选择，因此优先安排会议先结束的才是合理的。

然后接着在剩余的场次⾥判断会议开始时间是否在当前会议结束时间之后，如果在后⾯说明可以继续安排，下⾯就是代码实现。

（1）定义会议实体类，需要实现Comparable接⼝。

1/**2 * 会议类，需实现Comparable接⼝3*/4public class Meeting implements Comparable<Meeting>{5//定义会议属性6private int number;7private int starTime;8private int endTime;910//get set⽅法11public int getNumber() {12return number;13 }1415public void setNumber(int number) {16this.number = number;17 }1819public int getStarTime() {20return starTime;21 }2223public void setStarTime(int starTime) {24this.starTime = starTime;25 }2627public int getEndTime() {28return endTime;29 }3031public void setEndTime(int endTime) {32this.endTime = endTime;33 }3435//构造⽅法36public Meeting(int number, int starTime, int endTime) {37this.number = number;38this.starTime = starTime;39this.endTime = endTime;40 }4142 @Override43public String toString() {44return "Meeting{" +45 "number=" + number +46 ", starTime=" + starTime +47 ", endTime=" + endTime +48 '}';49 }50//需要重写接⼝的⽅法51 @Override52public int compareTo(Meeting o) {53//按照会议结束时间升序排列54if(this.endTime>o.endTime){55return 1;56 }57if(this.endTime<o.endTime){58return -1;59 }60return 0;61 }62 }（2）测试类，⾥⾯实现动态规划算法。

算法设计贪心算法的思想与实现算法是计算机科学领域中的核心概念，它指导着解决问题的方法和步骤。

贪心算法是一种常用的算法设计思想，它在求解最优化问题时，每一步都采取当前状态下最优的选择，希望得到全局最优解。

本文将介绍贪心算法的思想和实现方式，并通过一个实际问题的案例来说明其应用。

一、贪心算法的思想贪心算法是一种贪心思想的应用，即每一步都做出在当前看来最好的选择。

它不关心整体的结果，只关心当下最优解。

贪心算法通常可以通过以下三个步骤实现：1. 贪心选择策略：在每一步中，通过一定的策略选择当前看来最优的解。

2. 确定限制条件：确定所得到的选择是否满足问题的限制条件。

3. 最优子结构：通过贪心选择策略，将原问题分解为若干子问题，每个子问题都具有最优子结构。

贪心算法的核心思想在于每一步都是局部最优解，通过一系列局部最优解，最终得到全局最优解。

然而，贪心算法并不能保证得到全局最优解，只适用于满足贪心选择策略、具有最优子结构和无后效性的问题。

二、贪心算法的实现贪心算法的实现通常分为以下几个步骤：1. 建立数学模型：通过数学表达式对问题进行建模。

2. 确定贪心选择策略：根据问题的特点和要求，确定一种贪心选择策略。

3. 构造贪心算法：根据贪心选择策略，构造出一个贪心算法来求解问题。

4. 证明算法的正确性：通过数学证明等方式，证明贪心算法得到的解是问题的最优解。

三、贪心算法的应用贪心算法可以应用于众多实际问题的求解，例如最小生成树、最短路径、背包问题等。

下面以活动选择问题为例来说明贪心算法的应用。

假设有n个活动，每个活动都有一个开始时间和结束时间。

要求从这些活动中选择出最多的互不冲突的活动（即活动之间不能出现时间上的重叠），请设计一个贪心算法来解决该问题。

算法步骤：1. 将活动按照结束时间的先后顺序进行排序。

2. 选择第一个活动作为已安排的活动。

3. 从剩余的活动中选择结束时间与已安排活动的开始时间不重叠的活动，将其加入到已安排的活动中。

贪心算法与动态规划算法的主要区别所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

这是利用贪心算法求解最优解的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

共同点：求解的问题都具有最优子结构性质差异点：动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。

Prim算法O(n2)首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i∈S，j∈V-S，且c[i][j]最小的边，将顶点j添加到S中。

这个过程一直进行到S=V时为止。

在这个过程中选取到的所有边恰好构成G的一棵最小生成树。

在上述Prim算法中，还应当考虑如何有效地找出满足条件i∈S, j∈V-S，且权c[i][j]最小的边(i,j)。

实现这个目的的较简单的办法是设置2个数组closest和lowcost。

在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closest[j])，最后将j添加到S中，并对closest和lowcost作必要的修改。

Kruskal算法O(eloge)首先将G的n个顶点看成n个孤立的连通分支。

将所有的边按权从小到大排序。

然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。

这个过程一直进行到只剩下一个连通分支时为止。

贪心算法理解贪心算法的基本原理和应用场景贪心算法：理解贪心算法的基本原理和应用场景简介：贪心算法（Greedy Algorithm）是一种常用的算法设计和解决问题的方法。

它以一种贪婪的方式做出每一步的选择，希望最终能够达到整体上的最优解。

本文将介绍贪心算法的基本原理和常见应用场景。

一、贪心算法的基本原理贪心算法的基本原理是每次都做出当前最优的选择，希望最终能够达到整体上的最优解。

贪心算法的优点在于简单、高效，但由于它只关注当前最优解，因此可能无法得到全局最优解。

贪心算法的基本步骤如下：1. 将问题划分为若干子问题，每个子问题都有多个选择；2. 分析子问题的选择，以及每个选择的最优解；3. 根据每个子问题的最优解，做出当前最优的选择；4. 更新已做出选择的子问题集合；5. 重复步骤3和4，直到解决全部子问题。

二、贪心算法的应用场景1. 零钱兑换问题零钱兑换问题是指给定一个金额和一组零钱的面值，如何用最少数量的零钱找零。

贪心算法可以从面值最大的零钱开始，每次找零选择当前面值最大的零钱，直到达到目标金额。

2. 区间调度问题区间调度问题是指给定一组区间，如何选择最多数量的不相交区间。

贪心算法可以根据区间的结束时间进行排序，每次选择结束时间最早的区间，并排除与之重叠的其他区间。

3. 背包问题背包问题是指给定一组物品和一个固定容量的背包，如何选择物品放入背包，使得背包中物品的总价值最大。

贪心算法可以通过计算每个物品的单位价值（即物品的价值与重量的比值）来选择单位价值最高的物品放入背包。

4. 最短路径问题最短路径问题是指在一个有向图或无向图中，找到两个节点之间的最短路径。

贪心算法可以使用Dijkstra算法，每次选择离起始节点最近的未访问节点进行扩展，直到找到目标节点。

5. 活动选择问题活动选择问题是指在一组活动中，选出最大的互相兼容的活动子集合。

贪心算法可以根据活动的结束时间进行排序，每次选择结束时间最早的活动，并排除与之重叠的其他活动。

动态规划和贪心算法的区别和优劣比较动态规划和贪心算法是两种经典的问题求解方法，本文将从定义、区别、优劣比较等方面来详细介绍这两种算法。

一、定义1.动态规划动态规划是一种将复杂问题分解成小问题来解决的算法。

将复杂的问题转化为一系列小问题，然后逐步解决每个小问题，最后将这些小问题的解合成总问题的解。

动态规划一般用于求解最优化问题，如求最长公共子序列、最长递增子序列以及最短路径等。

2.贪心算法贪心算法是一种贪心思想来解决问题的算法。

贪心算法的基本思想是，每步中都采取当前状态下最优的选择，希望从局部最优解的选择中得到全局最优解。

二、区别虽然两种算法的思想都是分解问题，但是两者在实现、时间复杂度等方面有着显著的区别，具体如下：1.实现动态规划算法一般需要用到递归或者记忆化搜索等技巧，其中递归算法通常需要很多空间存储中间结果，因此空间复杂度较高。

而贪心算法通常只需要一次遍历即可求解，因此实现较为简单。

2.时间复杂度动态规划算法的时间复杂度一般较高，通常是指数量级。

而贪心算法的时间复杂度较低，通常是常数级别，因此时间效率较高。

3.解决问题的特点动态规划算法通常解决目标函数具有最优子结构性质的问题，即当前状态下的最优解包含以前状态下的最优解。

而贪心算法通常解决目标函数具有贪心性质的问题，如局部最优解能够推导出全局最优解等。

三、优劣比较动态规划算法和贪心算法在不同情况下具有不同的优劣性，如下所示：1.动态规划的优劣a.优点(1).解决所有具有最优子结构的问题。

(2).可以在时间复杂度为多项式级别，空间复杂度为常数级别的情况下求解问题。

(3).可以考虑状态转移方程中的所有状态，找到最优解。

b.缺点(1).实现比较困难，需要使用递归和记忆化搜索等技巧。

(2).需要很多空间存储中间状态。

(3).如果没有最优子结构，导致算法无法求解。

2.贪心算法的优劣a.优点(1).实现简单，易于理解。

(2).时间复杂度低，适合对实时性要求较高的问题。

贪⼼算法和动态规划的区别与联系
联系
1.都是⼀种推导算法
2.都是分解成⼦问题来求解，都需要具有最优⼦结构
区别
1.贪⼼：每⼀步的最优解⼀定包含上⼀步的最优解，上⼀步之前的最优解则不作保留；
动态规划：全局最优解中⼀定包含某个局部最优解，但不⼀定包含前⼀个局部最优解，因此需要记录之前的所有的局部最优解
2.贪⼼：如果把所有的⼦问题看成⼀棵树的话，贪⼼从根出发，每次向下遍历最优⼦树即可（通常这个“最优”都是基于当前情况下显⽽易见的“最优”）；这样的话，就不需要知道⼀个节点的所有⼦树情况，于是构不成⼀棵完整的树；
动态规划：动态规划则⾃底向上，从叶⼦向根，构造⼦问题的解，对每⼀个⼦树的根，求出下⾯每⼀个叶⼦的值，最后得到⼀棵完整的树，并且最终选择其中的最优值作为⾃⾝的值，得到答案
3.根据以上两条可以知道，贪⼼不能保证求得的最后解是最佳的，⼀般复杂度低；⽽动态规划本质是穷举法，可以保证结果是最佳的，复杂度⾼。

4.针对0-1背包问题：这个问题应⽐较选择该物品和不选择该物品所导致的最终⽅案，然后再作出最好选择，由此就导出许多互相重叠的⼦问题，所以⽤动态规划。

从活动选择问题看动态规划和贪⼼算法的区别与联系这篇⽂章主要⽤来记录我对《算法导论》贪⼼算法⼀章中的“活动选择问题”的动态规划求解和贪⼼算法求解的思路和理解。

主要涉及到以下⼏个⽅⾯的内容：①什么是活动选择问题---粗略提下，详细请参考《算法导论》②活动选择问题的DP(Dynamic programming)求解--DP求解问题的思路③活动选择问题的贪⼼算法求解④为什么这个问题可以⽤贪⼼算法求解？⑤动态规划与贪⼼算法的⼀些区别与联系⑥活动选择问题的DP求解的JAVA语⾔实现以及时间复杂度分析⑦活动选择问题的Greedy算法JAVA实现和时间复杂度分析⑧⼀些有⽤的参考资料①活动选择问题给定N个活动，以及它们的开始时间和结束时间，求N个活动中，最⼤兼容的活动个数。

⽐如：活动 i: 1 2 3 4.....开始时间 si: 1 3 0 5....结束时间 fi: 4 5 6 7.....活动1的开始时间s(1)=1，结束时间f(1)=4，它与活动2是不兼容的。

因为，活动1还没有结束，活动2就开始了(s(2) < f(1))。

活动2 与活动4 是兼容的。

因为，活动2的进⾏区间是[3,5) ⽽活动4的进⾏区间是[5,7)⽬标是：在N个活动中，找出最⼤兼容的活动个数。

②活动选择问题的DP(Dynamic programming)求解1）建模活动 i ⽤ a(i)来表⽰，开始时间⽤ s(i)表⽰，结束时间⽤ f(i)表⽰，所有活动的集合为S定义⼀个合适的⼦问题空间，设 S(i,j) 是与 a(i) 和 a(j)兼容的活动集合。

S(i,j)={a(k), a(k) belongs to S: f(i)<=s(k)<f(k)<=s(j)}2）问题⼀般化(不是很理解)这⾥第⼀个活动和最后⼀个活动有点特殊。

为了完整表⽰问题，构造两个虚拟的活动: a(0) 和 a(n+1)其中,s(0)=f(0)=0，s(n+1)=f(n+1)=Integer.MAX_VALUE于是，S=S(0,n+1)，从N个活动中找出最⼤兼容的活动，就转化成了求解 S(0,n+1)集合中包含的最多元素个数3）⼦问题分析假设所有的活动都按结束时间递增排序。

背包问题贪心法和动态规划方案法求解嘿，大家好！今天咱们来聊聊那个让人又爱又恨的背包问题。

这个问题可是算法领域的经典难题，不过别怕，今天我会用贪心法和动态规划两种方法帮你轻松搞定它！来个简单直接的背景介绍。

背包问题，简单来说，就是给定一组物品，每个物品都有一定的价值和重量，你需要在不超过背包承载重量的前提下，挑选出价值最大的物品组合。

听起来是不是有点像生活中的购物决策？哈哈，没错，这就是背包问题的魅力所在。

好，下面咱们直接进入主题。

一、贪心法贪心法，顾名思义，就是每一步都选择当前看起来最优的方案。

对于背包问题，贪心法的核心思想就是：每次都选取价值密度最大的物品。

1.计算每个物品的价值密度，即价值除以重量。

2.然后，按照价值密度从大到小排序。

3.从排序后的列表中依次选取物品，直到背包装满或者没有物品可选。

二、动态规划法动态规划，这是一种更加严谨、也更复杂的方法。

它的核心思想是：通过把大问题分解成小问题，逐步求解，最终得到最优解。

1.定义一个二维数组dp[i][j]，表示在前i个物品中选择，背包容量为j时的最大价值。

2.我们考虑第i个物品是否放入背包。

如果放入，则前i-1个物品在容量为j-w[i]时的最大价值加上w[i]的价值，即dp[i][j]=dp[i-1][j-w[i]]+w[i]。

如果不放入，则前i-1个物品在容量为j时的最大价值，即dp[i][j]=dp[i-1][j]。

3.通过比较这两种情况，取最大值作为dp[i][j]的值。

整个过程中，我们需要遍历所有物品和所有可能的背包容量，最终得到dp[n][W]就是我们要找的最大价值。

现在，让我们用一段代码来具体实现一下动态规划法：defknapsack(W,weights,values):n=len(values)dp=[[0for_inrange(W+1)]for_inrange(n+1)]foriinrange(1,n+1):forjinrange(1,W+1):ifj>=weights[i-1]:dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i-1]]+values[i -1])else:dp[i][j]=dp[i-1][j]returndp[n][W]测试数据W=50weights=[10,20,30]values=[60,100,120]print(knapsack(W,weights,values))怎么样？是不是觉得动态规划法虽然复杂，但逻辑清晰，更容易找到最优解？通过上面的分析，我们可以看到，贪心法简单高效，但有时候并不能得到最优解；而动态规划法虽然计算复杂度较高，但可以得到最优解。

贪婪的动态规划——浅谈贪心思想在动态规划中的应用浙江省绍兴县柯桥中学黄劲松【关键字】贪心法，动态规划，状态，时间复杂度【摘要】贪心法和动态规划是信息学竞赛中的两种常用算法，本文着重讨论了贪心的思想是如何巧妙的运用到动态规划的解题中的。

全文分三个部分，首先讨论了贪心思想运用到动态规划解题中的可行性和必要性，然后就贪心思想在动态规划中的两种基本应用分别做了举例说明，最后总结全文。

【正文】引言贪心法和动态规划是信息学竞赛中的常用经典算法，而当某些问题的模型过于复杂的时候，由于状态过于庞大、转移困难等一系列的问题，常规的动态规划难于甚至无从下手。

而在这个时候，巧妙的使用贪心思想，将其融入到动态规划的解题中，动态规划便焕发出了新的光彩。

1、贪心思想运用到动态规划中的必要性和可行性动态规划的原理是：在求解问题的过程中，通过处理位于当前位置和所达目标之间的中间点来找到整个问题的解。

整个过程是递归的，每到一个新的中间点都是已访问过的点的一个函数。

适合于动态规划法的标准问题必须具有下列特点：●1、整个问题的求解可以划分为若干个阶段的一系列决策过程。

●2、每个阶段有若干可能状态。

●3、一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。

●4、在任一个阶段，最佳的决策序列和该阶段以后的决策无关。

●5、各阶段状态之间的转换有明确定义的费用在实际的动态规划的解题中，面临着两大困难：一是不知道题目是否可以用动态规划求解；二是即使能够想到用动态规划来求解，但是因为种种因素，算法的效率并不乐观。

这个时候，使用贪心思想分析问题，可以让你在山穷水尽疑无路的时候，柳暗花明又一村。

在运用贪心思想的时候，主要是分析出问题的一些本质，或者分析出低效算法的一些冗余。

当然，我们要根据题目的特殊信息，合理的运用好贪心思想，才能帮助动态规划发挥其强大的功效。

下文就贪心思想如何解决动态规划面临着的这两大困难分别做了举例说明。

2、贪心思想在动态规划中的应用一：确立状态动态规划当中，状态的确立是重点，而在实际的解题过程中，状态的信息往往是隐含的，这个时候，合理的运用贪心思想，可以迅速的从繁芜丛杂的问题背景中巧妙地抽象出状态。

动态规划与贪⼼算法的区别动态规划：动态规划应⽤于⼦问题重合的情况，不同的⼦问题具有相同的⼦⼦问题，动态规划算法将每个⼦问题求解⼀次，将其解保存在⼀个表格中，需要时进⾏调⽤。

刻画⼀个最优解的结构特征。

递归的定义最优解的值。

计算最优解的值，有⾃顶向下和⾃底向上的⽅法，通常采⽤⾃底向上的⽅法。

⼀、DP思想：1、把⼀个⼤的问题分解成⼀个⼀个的⼦问题。

2、如果得到了这些⼦问题的解，然后经过⼀定的处理，就可以得到原问题的解。

3、如果这些⼦问题与原问题有着结构相同，即⼩问题还可以继续的分解。

4、这样⼀直把⼤的问题⼀直分下去，问题的规模不断地减⼩，直到⼦问题⼩到不能再⼩，最终会得到最⼩⼦问题。

5、最⼩⼦问题的解显⽽易见，这样递推回去，就可以得到原问题的解。

贪⼼算法：每⼀步都做出当时看起来最佳的选择，也就是说，它总是做出局部最优的选择。

贪⼼算法的设计步骤：对其作出⼀个选择后，只剩下⼀个⼦问题需要求解。

证明做出贪⼼选择后，原问题总是存在最优解，即贪⼼选择总是安全的。

剩余⼦问题的最优解与贪⼼选择组合即可得到原问题的最优解。

联系：都是分解成⼦问题来求解，都需要具有最优⼦结构所有的贪⼼问题都可以⽤动态规划来求解，可以这么说，贪⼼算法是动态规划的特例。

区别：1.贪⼼：每⼀步的最优解⼀定包含上⼀步的最优解，上⼀步之前的最优解则不作保留；动态规划：全局最优解中⼀定包含某个局部最优解，但不⼀定包含前⼀个局部最优解，因此需要记录之前的所有的局部最优解也就是说，假如你要求第⼗步的最优解，那么第⼗步的最优解肯定与第九步的最优解有关，⽽第九步的最优解肯定与第⼋步的最优解有关。

可以这么理解，贪⼼算法第⼗步的最优解得把前⾯九步的最优解都⽤上了，但是动态规划你需要求第⼗步的最优解，这个最优解可能只与第⼋步，第三步，第⼀步有关，与第九步没有关系，我们为什么选择第⼋步⽽不选择第九步呢？是因为我们在计算第⼗步的最优解的时候其实把1-9步的组合的情况都计算了，选择了其中最优的解，也就是第⼋步的解，其实第⼗步解的构成与第九步没有关系，动态规划相当于穷举了1-9步最优情况下的组合，选了其中最优的作为第⼗步的最优解，⽽贪⼼算法第⼗步的最优解肯定是由第九步构成的。