数据结构与算法之动态规划浅讲

冷不防 2023-07-14 05:42 46阅读 0赞

make it work, make it right, make it fast!
即从递归（效率往往不能让人满意）到 迭代！

斐波那契数列：
最low递归解法：
第43项 需要1秒
第67项 需要1天
第92项 需要3生三世
所以严格意义上来讲，这根本不算是一个算法！

  1. int fib(n) {
  2.      return (2 > n) ? n : fib(n-1) + fib(n-2);}

很明显这和上到第N个台阶（每次上1个或2个）有多少种方法是一样的。
实现方法中有有大量重复计算和递归。因此我们怎么解决呢？
最容易想到的方法就是把之前算过的数存下来，然后当需要用的时候取出来。
迭代： 以下方法越来越好，嘿嘿

  1. 记忆（memoization）
    将已计算过实例的结果制表备查。

  2. 动态规划（dynamic programing）
    颠倒计算方向：由自顶向下递归，改为自底而上的迭代。

    //T(n) = O(n) 只需要O(1)的空间
    f = 0; g = 1; //fib(0), fib(1)
    while (0 < n—){

    1. g = g + f;
    2. f = g - f;

    }
    return g;

发表评论

表情：
评论列表 （有 0 条评论，46人围观）

还没有评论，来说两句吧...

相关阅读