逼近动态规划

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

是的，这是动态规划:从基本案例到最终案例。当然，您的示例(阶乘)太简单了，所以您可以自己简化许多事情:您消除了递归，并且从未在回忆录中使用测试。但不管怎么说就是这样。

关于回忆录的总体方案，见http://en.wikipedia.org/wiki/Memoization。

有关动态编程的说明，请参阅programming，您将能够阅读关于Fibonacci序列及其使用自下而上方法计算的部分。

Answer 2

是的，您解决问题的方法是一个非常简单的动态规划案例，您可以存储以前解决过的子问题，以帮助您解决实际问题。虽然您提供的示例将被视为动态编程，但它通常不被称为回溯

当有人说“回溯”()时，它通常涉及到自上而下的解决问题的方法，在这种方法中，您假设您已经通过以解决子问题的方式构造程序来解决了子问题。您可以存储这些子问题的结果，或者回忆录，这样它们就不会被多次计算。

让我通过一个例子来说明回溯：

下面是一个计算数字的第n个斐波纳契的简单例子：

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

上面的代码使用递归来求解sub-problems (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)。

如果我使用您的方法，Dynamic Programming来解决Fibonacci问题，它应该如下所示：

 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];
}

动态规划和记忆之间有更微妙的区别、权衡和暗示。有些人认为记忆是动态规划的一个子集。你可以在这里读到更多关于不同之处的内容：

Dynamic programming and memoization: bottom-up vs top-down approaches