时间戳

首页 > 解决方案 > 在递归 DP 中，通过存储变量来分解递归调用：效率低下？

c++ - 在递归 DP 中，通过存储变量来分解递归调用：效率低下？

问题描述

假设我正在递归地解决一个动态规划问题（自上而下）。例如，最长公共子序列问题的递归解决方案：

LCS(S,n,T,m)
{
if (n==0 || m==0) return 0;
if (S[n] == T[m]) result = 1 + LCS(S,n-1,T,m-1); 
else result = max( LCS(S,n-1,T,m), LCS(S,n,T,m-1) );
return result;
}

通常在这样的 DP 问题中，我们必须取一些表达式的最大值，表示返回到我们可以做出的不同选择。在上面的例子中，我们有两个简单表达式的最大值，但在更糟糕的情况下，它可能是三个或四个涉及长函数调用的相当复杂的表达式的最大值。在这种情况下，我经常想给这些复杂的表达式赋予自己的变量名，以使代码更具可读性。在上述情况下，这意味着我会写

LCS(S,n,T,m)
{
if (n==0 || m==0) return 0;
if (S[n] == T[m]) result = 1 + LCS(S,n-1,T,m-1); 
else
    a = LCS(S,n-1,T,m);
    b = LCS(S, n, T, m-1); 
    result = max(a, b);
return result;
}

（在这个简化的情况下a并不b复杂，但在其他情况下它们是复杂的，并且 max 函数可能有更多的参数，所以这真的可以帮助它更容易理解。）

我的问题：这是一个糟糕的主意吗？据我了解，我正在向调用堆栈的每一层添加一个变量，我认为这可能是浪费。但另一方面，LCS(S,n,T,m)无论如何，在每一层它都必须计算临时变量（我是用 C++ 来考虑的），据我所知，这两种方式的成本可能没有太大差异。

如果这是一个糟糕的想法，是否有更有效的方法来分解复杂的递归函数调用以使其更具可读性？

标签： c++recursiondynamic-programmingtemporary-objects

解决方案

C++ 有“As-If”规则，它规定编译器可以做它想做的任何事情，只要可观察到的效果与标准定义的要发生的效果没有区别。在这种情况下，证明两个片段具有相同的含义是微不足道的，并且编译器可能会为两者发出相同的指令。

注意：您在这里没有进行动态编程，因为您没有记忆参数/结果对。

推荐阅读