Speeding up function with dynamic programming

Question

I have this program

//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);
    }

Is it possible to speed it up with dynamic programming?

I realized that this function works in O (2 ^ n)

I have to reduce the execution time by dynamic programming, but do not understand the concept.

Just ask for a push in the right direction.

Answer 1

While I can’t give an answer to your real question, I was intrigued by something completely different, namely the statement

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

, g. 100% , return , undefined.

, , , 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) . (return g++;) (return g + fun() + fun()). fun(). , g, != 0, , g = 0, . fun (n) g > 0 , g * , g = 0.

A (n) return fun (n) G (n) return if ( , 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, , stakx g. , .

Answer 4

OK. ( , ).

int fun(int h){
    if(h<=0){
         g++;
         return g;
    }
    int tmp1 = g;
    int tmp2 = fun(h-1);
    int tmp3 = fun(h-4);
    return tmp1+tmp2+tmp3;
}

g

g g.

int gun(int h, int g0){
    if(h<=0){
         return g0+1;
    }
    int tmp1 = g0;
    int tmp2 = gun(h-1, g0);
    int tmp3 = gun(h-4, tmp2);
    return tmp3;
}

What can be simplified into:

int gun(int h, int g0){
    if(h<=0){
         return g0+1;
    }
    return gun(h-4, gun(h-1, g0));
}

:

int fun2(int h, int g0){
    if(h<=0){
         return g0+1;
    }
    return g0+fun2(h-1, g0)+fun2(h-4, gun(h-1,g0));
}

fun2 , , , , , memoize ( ), .

. g0 , 0.

int gun2(int h){
    if(h<=0){
         return 1;
    }
    return gun2(h-4) + gun2(h-1);
}

fun3 g0, 0, , fun2. , , , .

int fun3(int h){
    if(h<=0){
         return 1;
    }
    return fun3(h-1)+fun2(h-4, gun2(h-1));
}