作为动态规划的迭代解
维基百科说这是关于动态编程的：
在数学、计算机科学、经济学和生物信息学中，动态规划是一种解决复杂问题的方法，它将复杂的问题分解成一组简单的子问题。它适用于具有重叠子问题和最优子结构性质的问题。在适用的情况下，与其他没有利用子问题重叠的方法(比如深度优先搜索)相比，该方法花费的时间要少得多。
我还从Introduction to Algorithms (Cormen)了解到，dynamic programming是一种用于解决有already been computed once的repeating computations的方法。用外行人的话来说，
如果你要一次又一次地计算，最好把它存储在某个地方。
将此应用于Fibonacci，我可以编写其算法如下：
arr[3] = {1,1,1} //first two index for computation , last to keep track
fibbDyn(n){
if(n>=1 || a[2]>n ) return n; // return on base conditions
else {
res = arr[0] + fibbDyn(n-1);
arr[0]=arr[1];
arr[1]=res;
arr[2]+=1; // increment value by 1
return res;
}
} 虽然我相信这个算法遵循动态规划的例子，因为它减少了在原始递归版本中所做的额外计算：
fibb(n){
if (n>=1)return n;
else return fibb(n-1) + fibb(n-2);
}正如这里所述，由于每个递归步骤都有两个单独的调用，因此重复了许多计算。
迭代解决方案可能如下所示：
int FibonacciIterative(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
int prevPrev = 0;
int prev = 1;
int result = 0;
for (int i = 2; i <= n; i++)
{
result = prev + prevPrev;
prevPrev = prev;
prev = result;
}
return result;
}所以我的问题是，斐波纳契问题的迭代解会被归类为动态规划吗？
我不同意的理由是，迭代解决方案不显示Overlapping subproblems，例如递归解决方案。在迭代解决方案中，不需要进行冗余和重复的计算，因此不应该将其包含在动态规划中。
相关文章：http://en.wikipedia.org/wiki/Optimal_substructure，http://en.wikipedia.org/wiki/Overlapping_subproblems，http://en.wikipedia.org/wiki/Dynamic_programming。
回答 2
Stack Overflow用户
发布于 2015-05-11 18:30:50
是。这只是自下而上动态规划的特例。您可以丢弃您知道永远不会再次使用的表条目，对于Fibonacci来说，这意味着您只需要保留2个条目，然后您就可以忘记它曾经是一个表，只需使用两个命名变量。所以，结果看起来不一样，几乎太简单了。但是该算法的结构仍然是DP。您说不存在的重叠子问题仍然存在，因为每个结果都要使用两次(一次是在prev中，另一次是在prevPrev中)，最后除外。当然，不存在冗余计算，但这就是DP的思想--通过重用消除冗余计算。
对于允许动态规划的问题，有一个一般的“攻击计划”，即
- 递归地陈述问题
- (证明DP可以应用)
- 确定子问题的排序，使其按拓扑排序(因此，计算解决方案仅依赖于琐碎的解决方案和先前计算的解决方案，而不是未来的解决方案)。
- 如果有一个很好的顺序，按这个顺序迭代填充一个表。如果订单是烦人的，也许保持自上而下的结构。
在Fibonacci的例子中，所发生的事情是，顺序是微不足道的(这甚至并不罕见，但它使我们看起来“没有做什么特别的事情”)，并且依赖关系永远不会返回超过两个位置，所以表中唯一需要记住的部分是前两个单元格。因此，应用所有这些，你得到了著名的迭代算法。这并不意味着它不再是DP，它意味着DP是非常成功的。
至于属性(最优子结构，重叠子问题)，它们是问题的属性，不管你如何解决，它们都不会消失。但是，您仍然可以在迭代算法中看到它们，正如我在第一段中所指出的。
Stack Overflow用户
发布于 2015-05-11 19:23:23
在动态规划的维基百科页面上读到- 计算机程序设计中的动态规划。这就解释了这两种方法:自顶向下作为问题的递归公式出现的方法和自下而上的方法，在这两种方法中，我们迭代地生成更大问题的解决方案，而当前的解决方案存储在表中。在这种情况下，不需要一个表，并且可以使用两个变量来完成任务。因此，在迭代方法中，只使用两个变量来保存子问题的值，即prev, (i-1 th)和prevPrev, (i-2 th)。在这里，使用prev和prevPrev来求解第i次迭代(更大的问题)。
result = prev + prevPrev;它只不过是i迭代结果的表示，它等于prev(i-1) + prevPrev(i-2)。因此，子问题的重用也发生在迭代方法中。这是动态规划的自下而上方法，递归方法是动态规划的自顶向下方法。
https://stackoverflow.com/questions/30174943
复制相似问题
腾讯云开发者
