接近动态规划

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

记忆化的方法是否正确？因为，动态规划涉及递归。但我在这里没有包含它。所以我不确定我的方法是否正确。

- xxx

---

为什么你不确定？在我看来，这绝对是否定的。fact() 应该是一个递归函数，正如所需。 - Sourav Ghosh

所以你能告诉我这里出了什么问题吗？ - xxx

fact() 应该是一个递归函数。 - Sourav Ghosh

这里实际上没有什么问题。唯一的错误是数组大小不正确，请将其声明为 f[n+1]。 - Jean-Baptiste Yunès

@Jean-BaptisteYunès，为什么数组应该是n+1？所有dp算法都使用n+1的数组。我不明白原因是什么？ - xxx

C 数组的索引从 0 到 n-1。如果你想使用 f[n]，那么数组必须有 n+1 个元素。 - Jean-Baptiste Yunès

Answer 1

是的，您解决问题的方法是动态规划的一个非常简单的案例，其中您存储先前解决的子问题以帮助您解决实际问题。虽然您提供的示例被认为是动态规划，但通常不称为记忆化。

当有人说记忆化时，通常涉及自上而下的解决问题方法，您假设已通过以递归方式解决子问题的方式构建程序来解决子问题。您存储或记忆这些子问题的结果，以便它们不会被多次计算。

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

以下是计算数字的第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）。

虽然这段代码看起来很优雅，但运行时间是指数级的，因为可以多次解决i小于n的数字的fib（i）。您可以查看此处呈现的图表，以查看此问题生成的树：http://www.geeksforgeeks.org/program-for-nth-fibonacci-number。

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

以下是使用记忆化计算第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];
}

动态规划和记忆化之间存在更微妙的差异、权衡和影响。有些人认为记忆化是动态规划的一个子集。您可以在此处阅读有关差异的更多信息：

动态规划和记忆化：自底向上 vs 自顶向下

- Han Sheng Huang

---

如果我需要计算10^9的斐波那契数列，该怎么办？我认为这个解决方案行不通，因为当你声明长度为10^9+1的数组时，会出现java.lang.OutOfMemoryError: Java heap space错误。有更好的方法吗？ - Akhilesh Dhar Dubey

Answer 2

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

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

关于动态规划的解释，请参见http://en.wikipedia.org/wiki/Dynamic_programming，你将能够阅读有关斐波那契数列及其使用自下而上方法计算的部分。

- Jean-Baptiste Yunès