A geek

斐波拉契数列之动态规划算法

  1. 问题：

    https://baike.baidu.com/item/斐波那契数列/99145

    有一对兔子，从出生后的第3个月起每个月都生一对兔子。
小兔子长到第3个月后每个月又生一对兔子，假设所有的兔子都不死，问40个月内每个月的兔子总数为多少？
幼仔对数=前月成兔对数
成兔对数=前月成兔对数+前月幼仔对数
总体对数=本月成兔对数+本月幼仔对数
依次类推可以列出下表：
经过月数 1 2 3 4 5 6 7  8  9  10 11 12 
幼仔对数 1 0 1 1 2 3 5  8  13 21 34 55
成兔对数 0 1 1 2 3 5 8  13 21 34 55 89
总体对数 1 1 2 3 5 8 13 21 34 55 89 144

  2. 递归算法：

    #!/usr/bin/env python
# -*- coding: utf-8 -*-
def fib(n):
    if n <= 2:
        return 1 
    else:
        return fib(n - 1) + fib(n - 2)
r = fib(40)
#print(r)

    耗时：

    time python fib_recurse.py 
real	0m23.555s
user	0m23.499s
sys	0m0.045

  3. 动态规划算法:

    #!/usr/bin/env python
# -*- coding: utf-8 -*-
f = {}
def fib(n):
    global f
    result = 0
    if(n < 1):
        return -1
    else:
        if(n == 1 or n == 2):
         return 1
        else:
         if f.has_key(n):
                return f[n]
            else:
                f[n] = fib(n-1) + fib(n-2)
                return f[n]
r = fib(40)

    耗时：

    time python fib_dp.py 
real	0m0.037s
user	0m0.014s
sys	0m0.020s

  4. Ref:

Search

    Table of Contents