Speeding up a function with dynamic programming
c++, dynamic-programming
Solution
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.
Problem
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.