一、动态规划

1.算法思想

动态规划（Dynamic programming，简称DP）；核心思想是把原问题分解成子问题进行求解，也就是分治的思想。

那么什么问题适合用动态规划呢？我们通过一个现实中的例子，来理解这个问题。大家可能在公司里面都有一定的组织架构，可能有高级经理、经理、总监、组长然后才是小开发，今天我们通过这个例子，来讲讲什么问题适合使用动态规划。又到了一年一度的考核季，公司要挑选出三个最优秀的员工。一般高级经理会跟手下的经理说，你去把你们那边最优秀的3个人报给我，经理又跟总监说你把你们那边最优秀的人报给我，经理又跟组长说，你把你们组最优秀的三个人报给我，这个其实就动态规划的思想！

2. 算法特点

（1）求解最优解问题。

（2）整体问题的最优解依赖各子问题的最优解。即最优子结构，最优解肯定是有最优的子解转移推导而来，子解必定也是子问题的最优解。甲总监下面最优秀的3个人肯定是从X,Y,Z提交上来的3份名单中选择最优秀的三个人。例如Q哥是X组长下面的第5名，那么他肯定不可能是甲总监下面最优秀的三个。

（3）重叠子问题：我们将大问题分解 为小问题，这些小问题之间还有相互重叠的更小的子问题。不同的问题，可能都要求1个相同问题的解。假如A经理想知道他下面最优秀的人是谁，他必须知道X,Y,Z,O,P组最优秀的人是谁， 甲总监想知道自己下面最优秀的人是谁，也要去知道X,Y,Z组里面最优秀的人是谁？这就有问题重叠了，两个人都需要了解X,Y,Z三个小组最优秀的人。

（4）无后效性：求出来的子问题并不会因为后面求出来的改变。我们可以理解为，X组长挑选出三个人，即便到了高级经理选出大部门最优秀的三个人，对于X组来说，最优秀的还是这3个人，不会发生改变。

（5）从上往下分析问题，从下往上求解问题。

3.求解过程

动态规划问题，大致可以通过以下四部进行解决。

1.划分状态，即划分子问题，例如上面的例子，我们可以认为每个组下面、每个部门、每个中心下面最优秀的3个人，都是全公司最优秀的3个人的子问题。

2.状态表示，即如何让计算机理解子问题。上述例子，我们可以实用f[i][3]表示第i个人，他手下最优秀的3个人是谁。

3.状态转移，即父问题是如何由子问题推导出来的。上述例子，每个人大Leader下面最优秀的人等于他下面的小Leader中最优秀的人中最优秀的几个。

4.确定边界，确定初始状态是什么？最小的子问题？最终状态又是什么。例如上述问题，最小的子问题就是每个小组长下面最优秀的人，最终状态是整个企业，初始状态为每个领导下面都没有最优名单，但是小组长下面拥有每个人的评分。

具体步骤：

1、创建一个一维数组或者二维数组，保存每一个子问题的结果，具体创建一维数组还是二维数组看题目而定，基本上如果题目中给出的是一个一维数组进行操作，就可以只创建一个一维数组，如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值，比如背包问题中的不同物体的体积与总体积，找零钱问题中的不同面值零钱与总钱数，这样就需要创建一个二维数组。

注：需要创建二维数组的解法，都可以创建一个一维数组运用滚动数组的方式来解决，即一位数组中的值不停的变化，后面会详细徐叙述

2、设置数组边界值，一维数组就是设置第一个数字，二维数组就是设置第一行跟第一列的值，特别的滚动一维数组是要设置整个数组的值，然后根据后面不同的数据加进来变幻成不同的值。

3、找出状态转换方程，也就是说找到每个状态跟他上一个状态的关系，根据状态转化方程写出代码。

4、返回需要的值，一般是数组的最后一个或者二维数组的最右下角。

4.案例分析

（1）斐波那契数列

二、贪心算法

1.基本概念

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）

所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。

2.贪心算法的基本思路

• 建立数学模型来描述问题
• 把求解的问题分成若干个子问题
• 对每个子问题求解，得到子问题的局部最优解
• 把子问题的解局部最优解合成原来问题的一个解

3.该算法存在的问题

• 不能保证求得的最后解是最佳的
• 不能用来求最大值或最小值的问题
• 只能求满足某些约束条件的可行解的范围

4.贪心算法适用的问题

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

实际上，贪心算法适用的情况很少。一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可以做出判断。

5.贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

6.贪心算法的实现框架

从问题的某一初始解出发：
while (朝给定目标前进一步)
{
利用可行的决策，求出可行解的一个解元素。
}
由所有解元素组合成问题的一个可行解；

7.例题分析

三、动态规划和贪心算法的联系和区别

1.联系

• 都是一种推导算法

• 都是分解成子问题来求解，都需要具有最优子结构

2.区别

（1）贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解则不作保留；

动态规划：全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有的局部最优解

（2）动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常自顶向下的方式进行。

贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可（通常这个“最优”都是基于当前情况下显而易见的“最优”）；这样的话，就不需要知道一个节点的所有子树情况，于是构不成一棵完整的树；

动态规划：动态规划则自底向上，从叶子向根，构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，最后得到一棵完整的树，并且最终选择其中的最优值作为自身的值，得到答案

（3）根据以上两条可以知道，贪心不能保证求得的最后解是最佳的，一般复杂度低；而动态规划本质是穷举法，可以保证结果是最佳的，复杂度高。

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