CODEWITHSUNDEEP
c++dynamic-programming
aristotaly
aristotaly

Reputation: 399

Speeding up a function with dynamic programming

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 using dynamic programming?

I figured out that this function runs in O(2^n)

I am supposed to reduce the running time by dynamic programming, but do not understand the concept.

Just asking for a nudge in the right direction.

Upvotes: 5

Views: 358

Answers (4)

Ante
Ante

Reputation: 5448

If we define that summation order in g+fun(h-1)+fun(n-4) is from left to rigth, than this is good defined problem. With that I get values for fun(n), n=1,...,15:

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

Return value of fun(n) is evaluated as sequence of summations with not-descending elements. Each summand is for one larger then previous (return g++;) or same as previous (return g+fun()+fun()). Execution sequence of return statements depend only of fun() input parameter. So, with g set to initial value != 0 we get same summands as with g=0, but every summand is larger for same initial value. With that, fun(n) with initial g > 0 will return value that is g * number of executed return statements larger than with initial g = 0.

Define A(n) as number of executed return statements while executing fun(n), and G(n) number of executed return statement in if clause (same as number of g++ statement executions). For A and G holds:

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

From these observations it can be seen that for n > 0 holds:

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

Simple python implementation:

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: for expression g+fun(h-1)+fun(h-4) we can't have evaluation order guaranty, especially not in C.

Upvotes: 1

kriss
kriss

Reputation: 24157

OK. We start from fun (a serialized version where order of evaluation is forced).

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

Let's focus on g and forget the current result of the function

Now it is easy to change the function to pass in g as a parameter and to return the new value of g as a result.

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

Now back to fun:

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 does exactly the same thing as the initial fun, but now as we removed the side effect and the function only depends from it's parameter, we can memoize results (store already computed results in an array), which should speed-up the computing.

We can still simplify gun a bit. The g0 parameter is not really necessary, let's set it to 0.

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

We may even define a fun3 with g0 parameter fixed to 0, henceforth a bit simpler, but it still has to call fun2. I do not see yet how to simplify further but it's probably possible.

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

Upvotes: 0

Mohammad Mazaz
Mohammad Mazaz

Reputation: 316

Yes , It's possible to use DP to speed it up and avoid using CPU stack, but I agree with stakx about the side effect of changing the global static variable g. It's better to provide a mathematical expression because the recursive function above could give a different result depending on the order & count of calls.

Upvotes: 0

stakx - no longer contributing
stakx - no longer contributing

Reputation: 84725

While I can't give an answer to your actual question, I am intrigued by something altogether different, namely the statement

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

Obviously, your function has the side effect of changing the global static variable g. I am not 100% sure whether the return statement's expression actually evaluates in a clearly defined fashion, or whether the result might be undefined.

It might be a nice exercise to think about the order in which those function calls are executed, and how this affects g and thereby the function's result.

Upvotes: 7

Related Questions