1

下面的算法找到所有可能的方法来改变一个特定的总和真的使用记忆吗？

func count( n, m )
  for i from 0 to n
    for j from 0 to m
      if i equals 0
        table[i,j] = 1          
      else if j equals 0
        table [i,j] = 0
      else if S_j greater than i
        table[ i, j ] = table[ i, j - 1 ]
      else 
        table[ i, j ] = table[ i - S_j, j ] + table[ i, j - 1 ]
return table[ n, m ]

每次调用函数 count 时，它都会从头开始填充表。即使表已经针对某些值进行了初始化，下次调用 count 时，它也不会使用这些值，而是从 i = 0 和 j = 0 重新开始。

4

1 回答 1

1

这不是记忆。这是动态编程代码的示例。

为了分析你的代码，首先我们需要区分记忆和动态编程。

记忆是一种自上而下的方法，而动态编程是一种自下而上的方法。

考虑寻找数字n的阶乘问题。

如果你正在寻找 n! 通过使用以下事实，

n! = n * (n-1)! and 0!=1

这是自上而下方法的示例。

n 的值一直保存在内存中，直到值为 0！到（n-1）！被退回。缺点是浪费了大量的堆栈内存。优点是如果子问题已经解决，您不必重新计算子问题。子问题的解决方案存储在内存中。

但是在您的问题中，您没有自上而下的方法，因此没有记忆。

表中的每个条目都是直接从先前计算的子问题解决方案中获得的。它使用自下而上的方法。因此，您有一段使用动态编程的代码。

于 2013-04-14T10:48:51.627 回答