• 动态规划版的菲波那切数列 来分享一下

    2015/09/21 王先生 3 评论

刚才做了一道题关于菲波那切数列,本想着很简单的递归就能解决,结果运行总是超时,系统提示说用动态规划来解决,大家有什么好办法么

1 1 收藏


直接登录
最新评论
  • 你一定是使用了Up-Down的方式,中间涉及了大量的重复运算,这样的时间复杂度达到了指数级别,要超时。可以采用Bottom-Up的方法,从F(0)和F(1)开始计算,直到F(n),这样就避免了重复计算,达到了O(n)时间复杂度。当然进一步采用矩阵乘法优化可以达到O(lgn)

    • 王先生 学生 2015/09/21

      矩阵乘法怎么优化 能提供一下思路 或代码么

      • Bottom->up递归:
        F(n,a,b){
        F(n-1,b,a+b)
        }
        F(5,1,2)运行情况是:
        F(5,1,2)
        F(4,2,3)
        F(3,3,5)
        F(2,5,8)
        F(1,8,13){(结束条件)
        return b;
        }

        矩阵乘法:(没学过线性代数,直接跳到快速乘法部分)
        [fn | fn-1]
        = [fn-1 + fn-2 | fn-1]
        = [1 1 | 0 1] * [fn-2 | fn-1]
        = [1 1 | 0 1] * [ 0 1 | 1 0] * [fn-1 | fn-2]
        = [1 1 | 1 0] * [fn-1 | fn-2]
        so, [fn | fn-1] = [1 1 | 1 0]^(n-1) * [f1 | f0]
        问题就转化为了如何快速求[1 1 | 1 0]^(n-1),普通计算当然是O(n)

        快速乘法:
        用3的n次方(假设n=2^k;如果有单的,用个变量记下)做例子,矩阵的太麻烦了。
        3^(n/1)
        -> 9^(n/2)
        -> 81^(n/4)
        ….-> ?^(n/n)
        O(lgn)