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

Question

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

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 问题中，在某些时候我们必须取一些表达式的最大值，代表 returns 我们可以做出不同的选择。在上面的例子中，我们有两个简单表达式的最大值，但在更糟糕的情况下，它可能是三个或四个涉及长函数调用的非常复杂的表达式的最大值。在这种情况下，我常常想为这些复杂的表达式赋予它们自己的变量名，以使代码更具可读性。在上述情况下，这意味着我会写

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++，比如说），据我所知，成本可能没有太大差异在两种方式之间。

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

Answer 1

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

注意：您没有在此处执行动态规划，因为您没有记住参数/结果对。

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

In recursive DP, break up recursion call by storing variables: inefficient?

c++

recursion

dynamic-programming

temporary-objects