数据结构与算法 - 高级算法

本文探讨两个高级主题：动态规划 和 贪心算法。

【一】 动态规划

动态规划被认为是一种与递归相反的技术，递归是从顶部开始将问题分解。
1.使用递归解决问题虽然简洁，但是效率不高。包括JavaScript在内的众多语言，不能高效的将递归代码解析为机器代码，尽管写出来的代码简洁，但是执行效率低下。但并不是说使用递归是件坏事。
2.本质上，只是那些指令式编程语言和面向对象的编程语言对递归的实现不够完善（它们没有将递归作为高级编程的特性）。
3.许多使用递归去解决的编程问题，可以重写为使用动态规划的技巧去解决。动态规划方案通常会使用一个数组来简历一张表，用于存放被分解成众多子问题的解。

下边看一个菲波那切数列的例子：

1.动态规划实例：计算菲波那切数列

0,1,1,2,3,5,8,13,21,34,55，…

该序列是由前两个数值相加而成的。这是一个简单的递归函数。
JavaScript代码：

function recurFib(n) {
   if (n < 2) {
      return n;
   }
   else {
      return recurFib(n-1) + recurFib(n-2);
   }
}

上边的算法，有太多值在递归调用中被重新计算。我们使用动态规划的技巧来设计效率更高的算法。

function dynFib(n) {
    var val = [];
    for (var i = 0; i <= n; ++i) {
        val[i] = 0;
    }
    if (n == 1 || n == 2) {
        return 1;
    }
    else {
        val[1] = 1;
        val[2] = 2;
        for (var i = 3; i <= n; ++i) {
            val[i] = val[i-1] + val[i-2];
        }
        return val[n-1];
    }
}

未完待续…