dynamic programming: speeding up this function

Posted by aristotaly on Stack Overflow See other posts from Stack Overflow or by aristotaly
Published on 2010-04-27T20:36:33Z Indexed on 2010/04/27 21:03 UTC
Read the original article Hit count: 252

Filed under:
|
|

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 fugured out this function runs in O(2^n) it means that i suppose to reduce this time but the trouble is that i don get the idea of dinamic programming even a leading hint or a useful link to a resource will do

it is a work assingment
i do not ask for the solution :) just asking for the right direction

© Stack Overflow or respective owner

Related posts about dynamic-programming

Related posts about c++