进行动态编程

Question

我编写了一个小程序，使用动态编程技术来计算数字的阶乘。

#include<stdio.h>

int fact(int n)
{
    int f[n],i;
    f[0] = 1;

    for(i=1;i<=n;i++)
        f[i] = i * f[i-1];
    return f[n];
}

int main(void)
{
    printf("\n Factorial of %d is %d ",5,fact(5));
    return 0;
}

记忆方法正确吗？因为，动态编程涉及递归。但是我没有在这里包括它。所以我不确定我的方法。

Answer 1

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

当有人说记忆化，它通常涉及到的解决问题，你认为你已经解决了一个自上而下的方法子问题，通过结构中，将解决子问题的方式你的程序递归。您存储，或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];
}

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

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

Answer 2

是的，这就是动态规划：从基本情况到最终情况。当然，你的例子（阶乘）太简单了，所以你已经能够自己简化很多事情：你消除了递归并且从不在记忆中使用测试。但无论如何就是这样。

有关记忆化的一般方案，请参阅http://en.wikipedia.org/wiki/Memoization。

有关动态编程的说明，请参阅http://en.wikipedia.org/wiki/Dynamic_programming，您将能够阅读有关斐波那契数列及其使用自下而上方法的计算的部分。