【算法导论】贪心算法，递归算法，动态规划算法总结

一般实际生活中我们遇到的算法分为四类：

一>判定性问题

二>最优化问题

三>构造性问题

四>计算性问题

而今天所要总结的算法就是着重解决 最优化问题

《算法之道》对三种算法进行了归纳总结，如下表所示：

标准分治

动态规划

贪心算法

适用类型

通用问题

优化问题

优化问题

子问题结构

每个子问题不同

很多子问题重复（不独立）

只有一个子问题

最优子结构

不需要

必须满足

必须满足

子问题数

全部子问题都要解决

全部子问题都要解决

只要解决一个子问题

子问题在最优解里

全部

部分

部分

选择与求解次序

先选择后解决子问题

先解决子问题后选择

先选择后解决子问题

分治算法特征：

1）规模如果很小，则很容易解决。//一般问题都能满足

2）大问题可以分为若干规模小的相同问题。//前提

3）利用子问题的解，可以合并成该问题的解。//关键

4）分解出的各个子问题相互独立，子问题不再包含公共子问题。 //效率高低

【一】动态规划：

依赖：依赖于有待做出的最优选择

实质：就是分治思想和解决冗余。

自底向上（每一步，根据策略得到一个更小规模的问题。最后解决最小规模的问题。得到整个问题最优解）

特征：动态规划任何一个i+1阶段都仅仅依赖 i 阶段做出的选择。而与i之前的选择无关。但是动态规划不仅求出了当前状态最优值，而且同时求出了到中间状态的最优值。

缺点：空间需求大。

【二】贪心算法：

依赖：依赖于当前已经做出的所有选择。

自顶向下（就是每一步，根据策略得到一个当前最优解。传递到下一步，从而保证每一步都是选择当前最优的。最后得到结果）

【三】分治算法：

实质：递归求解

缺点：如果子问题不独立，需要重复求公共子问题

动态规划和递归

最近在看《算法导论》，看到了动态规划一章。以前觉得动态规划总是要用递归的，看完前两节发现，不用递归也是可以的，而且效率可能更。不过动态规划虽然不需要总是递归，但大都是可以用递归的。

另外动态规划和贪心算法的区别是一个自底向上另一个自顶向下。

还有就是学到了memoization的概念，以前会这么用，现在系统化了一下。

递归和动态规划的转换

最近重新研读了下《挑战程序设计》对动态规划和递归的关系有了点新的理解，之前的理解过于机械化，单纯的以为根据递推公式可以直接写DP代码。

通俗的来说，

递归 是  考虑所有的情况，一般使用搜索（DFS /BFS）来实现。

在那些 可以转换为 DP 的递归算法中， 必定有很多重复的情况。

比如要做以下算术

1 + 1

1 + 1 + 1

2 + 1 + 1

3 + 1 + 1  

那么如果用遍历思维，也是符合人类习惯的思维之一，我们会：

1+1=2

1 + 1 =2  ;  2+1 =3

2 + 1 =3 ;  3+1 =4 ; 

3 + 1=4; 4+1 =5;  

共 7次。

而如果我们聪明点的话，我们可以把一些已经计算的过程记录下来

1+1 =2               =>                   add[1][1]= 2

add[1][1] =2     ;    2 +1 =3    =>           add[2][1] =3

add[2][1]=3  ;  3+1 = 4 =>  add[3][1] =4;

add[3][1] =4; 4+1=5  =>  add[4] [1] =5 ;

共 4次运算。因为add[][]是一个数字，可以直接返回。

可能 加法运算让大家感觉不到优势在哪里， 如果 把  + 号  当作是一个 很复杂的运算， 那么这种优化就十分有价值了。

这种优化方法 叫做  记忆化搜索 方法。

这种方法和 递归 剪枝  有本质的区别， 剪枝 法是把那些根本不可能的分枝去掉，而没有 对 遍历过程中存在的循环去掉，所以计算量等级上没有变化。

使用了 记忆化搜索 优化的递归算法，其时间复杂度 和  转换后的DP算法是一致的。

所以我们有以下定义成立：

一般可以使用记忆化搜索进行优化的递归算法，我们可以使用DP来进行优化。

至于如何公式化的，通用化的把 递归转变为 DP，还需要继续理解理解。

递归和动态规划

递归算法就是通过解决同一问题的一个或多个更小的实例来最终解决一个大问题的算法。为了在C语言中实现递归算法，常常使用递归函数，也就是说能调用自身的函数。递归程序的基本特征：它调用自身（参数的值更小），具有终止条件，可以直接计算其结果。

      在使用递归程序时，我们需要考虑编程环境必须能够保持一个其大小与递归深度成正比例的下推栈。对于大型问题，这个栈需要的空间可能妨碍我们使用递归的方法。

     一个递归模型为分治法，最本质的特征就是：把一个问题分解成独立的子问题。如果子问题并不独立，问题就会复杂的多，主要原因是即使是这种最简单算法的直接递归实现，也可能需要难以想象的时间，使用动态规划技术就可以避免这个缺陷。

     例如，斐波那契数列的递归实现如下：

    int F(int i)

    {

             if(i < 1)  return 0;

             if(i == 1) return 1;

              return F(i-1) + F(i - 2);

    }

    千万不要使用这样的程序，因为它的效率极低，需要指数级时间。相比之下，如果首先计算前N个斐波那契数，并把它们存储在一个数组中，就可以使用线性时间(与N成正比)计算F。

      F[0] = 0;F[1] = 1;

      for(i = 2; i