一、贪心算法
参考
算法（一）：贪心
我们今天介绍的主题是贪心算法。这是相对比较容易的一种算法。我这里不敢给出严格定义，因为我当年领悟贪心和动态规划的无后效性用了三年时间。从我第一次听说无后效性到终有一天恍然大悟，总共用去了一千天。所以，我这里就不讲定义，咱们直接看例子。
贪心算法，如果不用手动证明一个问题的数学性质的话，其实是比较简单的。
1.例1
有一个背包，其最大容量是50KG，现在有各种不同价值的液体，比方说，有水，其价值是10 每千克，共100KG；酒精，其价值是20 每千克，共30KG；有油，价值25每千克，共30KG。问什么样的方案才能使得背包里装的液体的总价值最大？显然，这是一道小学生都会的题目，拣贵的装呗。这谁不会。那就是把30KG油先装了，因为油最贵嘛，剩下20KG的容量装酒精，因为酒精比水贵。
好，那么，这个思维过程就是贪心：每一阶段做决策都找出当前条件下的最优解。当然这个问题，这种解法的正确性显而易见，贪心类的问题最难的地方在于正确性无法证明。这个我们先不管。毕竟我们不是在做算法研究，我们只要能用贪心去解决具体的编程问题就行了。
2.例2
再看一个简单的例子。在商店找零，比如说，售货员要找给你37块钱，那什么样的方案才是找钱的张数最少的方案呢？肯定是找回的零钱面值越大，最后的张数越少。所以我们可以使用贪心的方法来解决这个问题。先找一张20的，如果再找一张20的，那就超过37了，这不行，所以就再找一张10块的，然后是5块的和两张一块的。最终的方案就得到了，这也是一次典型的贪心计算方案。
3.例3
在贪心的思想的指导下，也设计了一种排序算法，这种算法被称为选择排序。排序的思想很简单。既然我的目标是把一堆数字从小到大排，那么我按阶段解决这个问题不就好了么？第一步找到最小的那个数把它放到第一位，第二步在剩下的所有数里再找最小的，把它放到第二位，依次类推。
二、分治算法 （divide and conquer,D&C）
参考
算法设计（二）：分治
一个小姑娘在图书馆借了一大摞书，抱着出门，警报响了，小姑娘正准备一本本地去试看是哪一本还没有消磁，管理员大妈惊呼：“这得试到什么时候了." 然后大妈就把书分了两半，去试一下没有响，再把剩下的那一半书再分两半。大妈的这种解法就叫分治。这也是算法设计的一个例子。小姑娘的解法的时间复杂度是O(n)，大妈解法的时间复杂度是O(log n)。当然，段子下面早就有人回复：如果不止一本书没有消磁，大妈解法就挂了。
分治算法，通过把问题分解为更小的子问题，先解决小问题，再把小问题的解合并起来的一种方法。通常，如果子问题的规模仍然很大，可以继续拆解成更小的任务，更进一步，实践中，大任务往往与子任务有相同的结构，以便于递归地进行任务拆解。
1.例1
以具体的例子来说明。现在一共9枚硬币，已知其中有一枚是假的，它比其他8枚都要轻。现在有一个天平，只称两次，能找到这枚硬币吗？
我们倒着想，假如现在有两枚，称一次，这很简单，天平高的那一边的是假币，如果有三枚呢？那就有两种情况，如果天平平衡，那么未称的那枚是假币，如果天平不平衡，高的那边是假币。
再往上一层，如果有9枚硬币，我们可以把它分为三堆，一堆3个，然后任选两堆放在天平上称，如果天平平衡，那么假币一定在没称的那一堆里，如果天平不平衡，那么假币就在天平高起的那一堆里。
这个例子就是一个很好的分治的例子，我们先把规模为9的大问题，分拆为规模为3的小问题，而且这个小问题与大问题保持了相同的性质。然后再去解决规模为3的小问题，就得到最终的答案了。
2.解题步骤
分治法有三个解题步骤，无论是简单的分治还是复杂的，都逃不开这个标准步骤。它们是：
- 拆解子任务
- 解决子任务
- 合并子任务的解
分治算法应用在方方面面，一般来说，解决子任务这一步骤相对容易，因为当子任务拆到规模一定小的情况下，解就会显得非常简单。分治算法的应用难点一般都会出现在拆解子任务与合并解的步骤上。
3.例2
给定一堆平面上的坐标，找出平面上的距离最近的点。暴力地一对对地去查找，这个办法的时间复杂度是O(n^2)，我们能不能使用分治来加速呢？实际上是可以的。但是这个问题的子问题分拆就没有那么简单了。
我们尝试着拆分一下，把这个平面一分为二，那么距离最小的点可能出现在左边，也可能出现在右边。假如，我们已经把左边最近的两个点找出来了，又把右边最近的两个点找出来了。那么合并这两个子问题的时候，只需要再比较这个子问题的解，看是哪一边的点更近。
但是等等，我们漏了一点东西。
看这幅图，假如，左边那个平面里，找到的最近的一对点是1和2，右边找到的最近的一对是3和4。解合并的时候，如果是检查1，2和3，4之间的距离谁更小是不行的，因为明显这个平面上，距离最近的一对点是2和3。也就是说在进行平面点的拆分的时候时候，就已经把2和3这一对最近的点拆开了，那么我们在合并的时候就要考虑这个问题。这个子问题的解合并是一个非常难的事情，这节课就不展开讲了。（以后还有没有机会再讲，看情况吧）
总之，使用分治算法解题的时候，如何正确地拆解问题，合并问题是设计算法的核心所在。
4.例3
所有的分治算法中，最常用的，还是二分法。二分通常可以使得问题的规模减半。
我们最常见的一个游戏，猜数字。我选定一个数字，在0到100之间，你来猜，如果猜得比选定数字大，我会提示你猜高了，如果比选定数字小，我会提示你猜低了。那么最多需要几次就一定能猜对呢？
我们常用的策略就是二分，先报50，如果主持人说低了，那我就知道，这个数字一定位于50，100这个区间，那我再报75。这样每次都能把待选区减少一半。所以最多需要7次就可以找到这个数字。如果是1到1000，只需要10次(从这里也可以看到O(log n)是一种时间复杂度很好的算法了，毕竟一百万地规模也只要20次。)
我们上面举的例子就是二分法，在一个已经有序的数组里进行查找，我们通常称之为二分查找(Binary Search)。
5.排序算法中最常用的快速排序和合并排序也是分治算法的经典案例
三、《算法图解》第9章 动态规划
1.简单算法
最简单的算法是尝试各种商品组合，并找出价值最高的组合。在有3件商品的情况下，需要计算8个不同的集合。在有4件时，需要计算16个集合。算法 复杂度达到了O(2^N)
2.贪婪算法
这个例子出现在《算法图解》第8章，背包只能装35磅，商品有以下3种可以偷：
- 音响 3000美元 30磅
- 电脑 2000美元 20磅
- 吉他 1500美元 15磅
贪心算法的原则就是挑最贵的去偷，装上30磅的音响，价值3000美元，别的东西就装不下了。
实际上，电脑加上吉他正好35磅，总计价值是3500美元。在这里，贪心策略显然不是最优解，但非常接近。
有些情况下，完美是优秀的敌人。如果只需要找到一个大致能解决问题的算法，就可以用贪心策略，它们实现起来非常容易，得到的结果又与正确结果相当接近。
3.动态规划
动态规划先解决子问题，再逐步解决大问题。每个动态规划算法都从一个网格开始，背包问题网格如下：
网格最初是空的，动态规划就是逐步将网格填满。
吉他行
第一个单元格表示背包的容量为1磅。 吉他的重量也是1磅， 这意味着它能装入背包！ 因此这个单元格包含吉他， 价值为1500美元。 来看下一个单元格，这个单元格表示背包的容量为2磅， 完全能够装下吉他！这行的其他的单元格也是如此，因为你目前只能把吉他装入背包，其他两种商品还未出现，所以第一行变成下图：
此时你可能心存疑惑：原来的问题说的是4磅的背包，为何要考虑容量为1磅、2磅等的背包呢？前面说过，动态规划从小问题着手，逐步解决大问题。这里解决的子问题将帮助你解决大问题。
音响行
现在来到第二行，在每一行，可偷的商品都是当前行的商品和之前各行的商品。因此，当前你已经解锁了音响和吉他，但是笔记本电脑还未解锁。现在来看第一个单元格，它表示容量为1磅的背包。 在此之前， 可装入1磅背包的商品的最大价值为1500美元。 背包的容量为1磅， 能装下音响吗？ 音响太重了， 装不下！ 由于容量1磅的背包装不下音响， 因此最大价值依然是1500美元。 接下来的两个单元格的情况与此相同。
现在来到了第四个单元格，也就是说背包容量为4磅，终于能装下音响，由于音响的价值为3000美元，比1500美元的吉他值钱多了，所以还是偷音响吧。
笔记本电脑行
下面以同样的方式处理笔记本电脑。 笔记本电脑重3磅， 没法将其装入容量为1磅或2磅的背包， 因此前两个单元格的最大价值还是1500美元。
对于容量为3磅的背包， 原来的最大价值为1500美元， 但现在你可选择盗窃价值2000美元的笔记本电脑而不是吉他， 这样新的最大价值将为2000美元！
现在来到这个问题最关键的单元格，对于容量为4磅的背包，当前的最大价值为3000美元， 你可不偷音响， 而偷笔记本电脑， 但它只值2000美元。但是笔记本电脑的重量只有3磅， 背包还有1磅的容量没用！ 在1磅的容量中， 可装入的商品的最大价值之前计算过。根据之前计算的最大价值可知， 在1磅的容量中可装入吉他， 价值1500美元。于是有了下面的比较：
于是我们得到了最终的结果：
现在你明白了为何要求解子问题吧？你可以合并两个子问题的解来得到更大问题的解。
4.背包问题FAQ:
增加第四件商品iphone，2000美元，1磅，要重新执行前面的计算么？
答案：不需要，再增加一行计算结果即可。沿着一列往下走时， 最大价值有可能降低吗？
答案： 不可能。 每次迭代时， 你都存储当前的最大价值。 最大价值不可能比以前低！行的排列顺序发生变化时结果将如何变化？
答案：没有变化。 也就是说， 各行的排列顺序无关紧要。可以逐列而不是逐行填充网格吗？
答案：就这个问题而言， 这没有任何影响， 但对于其他问题， 可能有影响。增加一件更小的商品将如何呢？
答案：单元格的按最小商品的重量划分。可以偷商品的一部分吗？
答案：没法处理。 使用动态规划时， 要么考虑拿走整件商品， 要么考虑不拿， 而没法判断该不该拿走商品的一部分。但使用贪婪算法可轻松地处理这种情况！ 首先， 尽可能多地拿价值最高的商品； 如果拿光了， 再尽可能多地拿价值次高的商品， 以此类推。动态规划可以处理相互依赖的情况吗？
答案： 没办法建模。 动态规划功能强大， 它能够解决子问题并使用这些答案来解决大问题。 但仅当每个子问题都是离散的， 即不依赖于其他子问题时， 动态规划才管用 。
计算最终的解时会涉及两个以上的子背包吗？
答案：根据动态规划算法的设计， 最多只需合并两个子背包， 即根本不会涉及两个以上的子背包。 不过这些子背包可能又包含子背包。最优解可能导致背包没装满吗？
答案：完全可能。
5.动态规划的启发
动态规划可帮助你在给定约束条件下找到最优解。 在背包问题中，你必须在背包容量给定的情况下， 偷到价值最高的商品。
在问题可分解为彼此独立且离散的子问题时， 就可使用动态规划来解决。要设计出动态规划解决方案可能很难， 这正是本节要介绍的。 下面是一些通用的小贴士。
- 每种动态规划解决方案都涉及网格。
- 单元格中的值通常就是你要优化的值。 在前面的背包问题中， 单元格的值为商品的价值。
- 每个单元格都是一个子问题， 因此你应考虑如何将问题分成子问题， 这有助于你找出网格的坐标轴。
6.小结
- 需要在给定约束条件下优化某种指标时， 动态规划很有用。
- 问题可分解为离散子问题时， 可使用动态规划来解决。
- 每种动态规划解决方案都涉及网格。
- 单元格中的值通常就是你要优化的值。
- 每个单元格都是一个子问题， 因此你需要考虑如何将问题分解为子问题。
- 没有放之四海皆准的计算动态规划解决方案的公式。
四、参考知乎 如何理解动态规划？
入门动态规划第一条：切忌望文生义，切忌用名字反推算法！如果我来命名，可能会取：分步规划，分步存储法， 递推存储法，数列递推法，状态转移法.....但我就是想不出动态规划啊。
1.能用动态规划解决的问题
如果一个问题满足以下两点，那么它就能用动态规划解决。
(1).问题的答案依赖于问题的规模，也就是问题的所有答案构成了一个数列。举个简单的例子，1个人有2条腿，2个人有4条腿，...， n 个人有多少条腿？答案是 2n 条腿。这里的 2n 是问题的答案， n 则是问题的规模，显然问题的答案是依赖于问题的规模的。答案是因变量，问题规模是自变量。因此，问题在所有规模下的答案可以构成一个数列 (f(1),f(2),...,f(n)) ，比如刚刚“数腿”的例子就构成了间隔为2的等差数列 (0,2,4,...,2n) 。
(2).大规模问题的答案可以由小规模问题的答案递推得到，也就是 f(n) 的值可以由 {f(i)|i<n} 中的个别求得。还是刚刚“数腿”的例子，显然 f(n) 可以基于 f(n-1) 求得： f(n)=f(n-1)+2 。
2.适合用动态规划解决的问题
能用动态规划解决，不代表适合用。比如刚刚的“数腿”例子，你可以写成 f(n)=2n 的显式表达式形式，那么杀鸡就不必用牛刀了。但是，在许多场景， f(n) 的显式式子是不易得到的，大多数情况下甚至无法得到，动态规划的魅力就出来了。
3.应用动态规划——将动态规划拆分成三个子目标
当要应用动态规划来解决问题时，归根结底就是想办法完成以下三个关键目标。
(1).建立状态转移方程
这一步是最难的，大部分人都被卡在这里。这一步没太多的规律可说，只需抓住一个思维：当做已经知道f(1) ~f(n-1) 的值，然后想办法利用它们求得 f(n) 。在“数腿”的例子中，状态转移方程即为f(n)=f(n-1)+2 。
(2).缓存并复用以往结果
这一步不难，但是很重要。如果没有合适地处理，很有可能就是指数和线性时间复杂度的区别。假设在“数腿”的例子中，我们不能用显式方程，只能用状态转移方程来解。如果现在 f(100) 未知，但是刚刚求解过一次 f(99) 。如果不将其缓存起来，那么求 f(100) 时，我们就必须花100次加法运算重新获取。但是如果刚刚缓存过，只需复用这个子结果，那么将只需一次加法运算即可。
(3).按顺序从小往大算
这里的“小”和“大”对应的是问题的规模，在这里也就是我们要从 f(0) , f(1) , ... 到f(n) 依次顺序计算。这一点在“数腿”的例子来看，似乎显而易见，因为状态方程基本限制了你只能从小到大一步步递推出最终的结果（假设我们仍然不能用显式方程）。然而当问题复杂起来的时候，你有可能乱了套，所以必须记住这也是目标之一。
4.高中数列题的魔改版
看到这里，你可能会觉得怎么跟高中的数列题那么像？？其实在我看来这就是高中数列题的魔改版。
高中的题一般需先推导出状态转移方程，再据此推导出显式表达式（在高中时代称为通项公式）。然而，动态规划是要我们在推导出状态转移方程后，根据状态转移方程用计算机暴力求解出来。显式表达式？在动态规划中是不存在的！
就是因为要暴力计算，所以前面说的目标有两个是涉及到代码层面上：
- 缓存中间结果：也就是搞个数组之类的变量记录中间结果。
- 按顺序从小往大算：也就是搞个for循环依次计算。
5.原文有3个例子，这里只引用第1个
斐波那契数列（简单）
斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
它遵循这样的规律：当前值为前两个值的和。
那么第 n 个值为多少？
首先，我们可以很容易得到状态转移方程： f(n)=f(n-1)+f(n-2) 。接下来我们用两种方法来做：
(1)简单递归(反例)
def fib(n):
if n < 2:
return n
else:
return fib(n-1) + fib(n-2)
if __name__ == '__main__':
result = fib(100)
# 你等到天荒地老，它还没有执行完
如上所示，代码简单易懂，然而这代码却极其低效。先不说这种递归的方式造成栈空间的极大浪费，就仅仅是该算法的时间复杂度已经属于 O(2^n) 了。指数级别时间复杂度的算法跟不能用没啥区别！
为什么是指数时间复杂度？图1通过展示求解 f(6) 的过程说明了其原因。如图，随着递归的深入，计算任务不断地翻倍！
(2).动态规划
def fib(n):
results = list(range(n+1)) # 用于缓存以往结果，以便复用（目标2）
for i in range(n+1): # 按顺序从小往大算（目标3）
if i < 2:
results[i] = i
else:
# 使用状态转移方程（目标1），同时复用以往结果（目标2）
results[i] = results[i-1] + results[i-2]
return results[-1]
if __name__ == '__main__':
result = fib(100)
# 秒算，result为：354224848179261915075
如上代码，针对动态规划的三个子目标，都很好地实现了（参考备注），具体为：
目标1，建立状态转移方程（完成）。也就是前面的 f(n)=f(n-1)+f(n-2) 。
目标2，缓存并复用以往结果（完成）。图1的简单递归存在大量的重复任务。在线性规划解法中，我们把结果缓存在results列表，同时在results[i] = results[i-1] + results[i-2]中进行了复用。这相当于我们只需完成图2中红色部分的计算任务即可，时间复杂度瞬间降为 O(n) 。
目标3，按顺序从小往大算（完成）。for循环实现了从0到 n 的顺序求解，让问题按着从小规模往大规模求解的顺序走。
5.【算法-动态规划】-最大子段和
动态规划算法与分治法类似，其基本思想也是将待求解问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适用与动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。
分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归的求解这些子问题，然后将各子问题的解合并得到原问题的解。
如果用分治法求解时，有些子问题被重复计算了许多次。如果我们能够保存已解决的子问题的答案，而在需要的时再找出已求得的答案这样就可以避免大量的重复计算，从而得到多项式时间算法。为了达到此目的，可以用一个表来记录所有已经解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思想。
问题描述：给定由n个正数（可能为负整数）组成的序列a1,a2,...,an,求该序列形如的子段和的最大值，当所有正数均为负整数时定义其最大字段和为0。
比如-2,11,-4,13,-5.-2，最大字段和是11+(-4)+13=20;6，-1，5，4，-7，其最大子段和为 6+(-1)+5+4
（1）找出最优解的性质，并刻画其结构特征
由b[j]的定义易知，当b[j-1]>0时b[j]=b[j-1]+a[j],否则b[j]=a[j]
（2）递归地定义最优值。
b[j]=max{b[j-1]+a[j],a[j]},1<=j<=n
（3）以自底向上的方式计算出最优值。
public class MaxSumClass3{
public static int MaxSum(int n,int[] a){
int sum=0,b=0;
for(int i=1;i<=n;i++){
if(b<0)b=a[i];
else b=b+a[i];
if(b>sum)
sum=b;
}
return sum;
}
public static void main(String[] args){
int n=6;
int[] a={0,-2,11,-4,13,-5,-2};
System.out.println(MaxSum(n,a));
}
}
