dynamic programming: speeding up this function

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

Answer 1

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.