#include <stdio.h>

int fib(int n, int * pbuf) {
    if(n > -1 && n < 3)
        return 1;
    else if(n < 0)
        return -1;
    if(!pbuf[n - 1])
        pbuf[n - 1] = fib(n - 1, pbuf);
    if(!pbuf[n - 2])
        pbuf[n - 2] = fib(n - 2, pbuf);
    return pbuf[n - 1] + pbuf[n - 2];
}

int main(void) {
    int buf[100] = {0};
    printf("%d\n", fib(5, buf));
    return 0;
}

由fib(5)的递归调用树来看，fib(3)、fib(2)、fib(1)都有优化的余地，但不知道我的算法对不对？请前辈指导一下。。。

[ 本帖最后由 lz1091914999 于 2011-7-26 13:58 编辑 ]

不错 不错 但是斐波那契数列不是动态规划题目  

楼主的方法就是动态规划的思想   去看看背包问题