使用动态编程加速函数

Question

我有这个程序

//h is our N
    static int g=0;
    int fun(int h){
        if(h<=0){
                  g++;
                  return g;
                  }
    return g+fun(h-1)+fun(h-4);
    }

有没有可能使用动态编程来加速它？

我计算出这个函数的运行时间为O(2^n)

我应该通过动态编程来减少运行时间，但我不理解这个概念。

只是在请求一个正确的方向上的推动。

Answer 1

虽然我无法回答你的实际问题，但我对一些完全不同的东西很感兴趣，即语句

return g+fun(h-1)+fun(n-4);

显然，您的函数有更改全局静态变量g的副作用。我不能百分之百确定return语句的表达式是否以一种明确定义的方式进行计算，或者结果是否可能是未定义的。

考虑一下这些函数调用的执行顺序，以及这对g和函数结果有何影响，这可能是一个很好的练习。

Answer 2

如果我们定义g+fun(h-1)+fun(n-4)中求和顺序是从左到右，那么这是一个定义良好的问题。这样我就得到了fun(n)，n=1，...，15的值：

3, 6, 10, 15, 33, 74, 154, 295, 575, 1143, 2269, 4414, 8508, 16396, 31634

fun(n)的返回值被计算为具有非降序元素的求和序列。每个被加数表示比前一个(返回g+fun()+fun()).；)大的一个或与前一个(返回g++;)相同return语句的执行顺序仅依赖于fun()输入参数。因此，当g设置为初始值!= 0时，我们得到与g=0相同的求和数，但对于相同的初始值，每个被加数都更大。这样，初始g> 0的fun(n)将返回值为g *比初始g=0大的已执行返回语句的数量。

定义A(n)为执行fun时执行的return语句数(N)，定义G(n)为if子句中执行的return语句数(与g++语句执行数相同)。对于A和G保持：

A(n) = A(n-1) + A(n-4) + 1
G(n) = G(n-1) + G(n-4)
A(n) = 1 and G(n) = 1, for n <= 0

从这些观察可以看出，对于n>0成立：

fun(n) = fun(n-1) + G(n-1) * A(n-4) + fun(n-4)

简单的python实现：

def x( h ):
  Rg = { -3:1, -2:1, -1:1, 0:1 }
  Ra = { -3:1, -2:1, -1:1, 0:1 }
  F  = { -3:1, -2:1, -1:1, 0:1 }
  for i in xrange( 1, h+1 ):
    F[i] = F[i-1] + Rg[i-1]*Ra[i-4] + F[i-4]
    print i, F[i]
    Rg[i] = Rg[i-1] + Rg[i-4]
    Ra[i] = Ra[i-1] + Ra[i-4] + 1

@stakx:对于表达式g+fun(h-1)+fun(h-4)，我们不能保证计算顺序，特别是在C中。

Answer 3

是的，可以使用DP来加速它并避免使用CPU堆栈，但我同意stakx关于更改全局静态变量g的副作用。最好提供一个数学表达式，因为上面的递归函数可能会根据调用的顺序和计数给出不同的结果。