进行动态编程

是的，您解决问题的方法是动态编程的一个非常简单的例子，您可以在其中存储先前解决的子问题来帮助您解决实际问题。虽然您提供的示例将被视为动态编程，但通常不称为“ 记忆化”

当有人说记忆化，它通常涉及到的解决问题，你认为你已经解决了一个自上而下的方法子问题，通过结构中，将解决子问题的方式你的程序递归。您存储，或memoize的，这些子问题，使他们不会被计算多次的结果。

让我通过一个例子说明记忆化：

这是计算数字的第n个斐波那契的简单示例：

int fib(int n)
{
   if (n <= 1)
      return n;
   return fib(n-1) + fib(n-2);
}

上面的代码使用递归来解决子问题（fib（n-1）和fib（n-2）），以便最终解决fib（n）。假定fib（n-1）和fib（n-2）已按照其构造方式求解。

尽管这段代码看起来不错，但是运行时间却是指数的，因为您可以多次求解fib（i），其中i是小于n的数字。您可以查看此处显示的图表，以查看由该问题生成的树：http : //www.geeksforgeeks.org/program-for-nth-fibonacci-number。

为了避免不必要的重新计算，记忆化用于通过使用内存来优化运行时。

这是一个使用Memoization计算第n个斐波那契数的优化示例：

/*Global array initialized to 0*/
int a[100];

int fib(int n)
{
    /*base case*/
    if (n <= 1) 
        return n;
    /*if fib(n) has not been computed, compute it*/
    if (a[n] == 0) {
        a[n] = fib(n - 1) + fib(n - 2);
    }
    */Otherwise, simply get a[n] and return it*/
    return a[n];
}  

如您所见，整体结构与递归解决方案并没有太大区别，但是它运行的是线性时间而不是指数时间，因为只有当我们尚未计算fib（i）时，才会进行计算。

如果我要对斐波那契问题使用您的方法“ 动态编程”，它将看起来像这样：

 int fib(int n)
 {
   /* just like the array you declared in your solution */
   int f[n+1];
   int i;

   /* set up the base cases, just like how you set f[0] to 1*/
  f[0] = 0;
  f[1] = 1;

   for (i = 2; i <= n; i++)
   {
       /* using previously solved problem to solve further problems*/
       f[i] = f[i-1] + f[i-2];
   }
     /*return the final result*/
   return f[n];
}

动态编程和记忆化之间还有更多细微的差异，折衷和含义。有些人认为记忆化是动态编程的子集。您可以在此处了解更多有关差异的信息：

动态编程和记忆：自下而上与自上而下的方法