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: 329
        
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