【算法设计与分析】fibonacci的动态规划实现

• 思路：动态规划就是用空间换取时间的一种想法，他把每个子问题的解存放下来，要使用某个子问题的解的时候，先去查看之前有没有算过，有算过就直接拿过来用，没有算过在进行计算，这样就避免了递归中重复计算相同问题解的过程。
• 满足下面条件的问题可以使用动态规划求解：
  • 子问题的数量是多项式级别的。
  • 原问题的解可以很容易的通过子问题的解来计算。
  • 各个子问题之间有特定的顺序，不需要同步来计算。

1、伪码

2、代码

#include <iostream>
#include <memory.h>
using namespace std;
int* M = NULL;
int fibonacci(int aaa)
{
  if(M[aaa] == -1)
    M[aaa] = fibonacci(aaa-1)+fibonacci(aaa-2);
  return M[aaa];
}

int top_down(int xxx)
{
  M = new int[xxx+1];
  memset(M,-1,(xxx+1)*sizeof(int));
  M[0] = 0;
  M[1] = 1;
  return fibonacci(xxx);
}
int main()
{
  cout<<top_down(5);
  if(M == NULL)
    delete []M;
  return 0;
}