dynamic programming problem

[bruk]

Hi! I have this problem and I am not sure how to solve it.
I have a vector of integers V and a number W.
Using all the numbers in V, I have to put between every number a plus or a minus or a multiplication so doing the calculations in V I get W.
between every number of V you have a parenthesis, so you don't have to worry about the precedence of operands.
for example:
V = 4 3 7 9
W =40

if I use + * - I get
4 + 3 * 7 - 9
But like I have parenthesis everywhere I get
((4 + 3) * 7) - 9 which is W so I get one solution.

I know it must be solved with dynamic programming, and I make this:

Code: Select all

void process(double v[],int n, double w,int c){
     int i;
     if(w==v[0]) {
          printf("ops =%c %c %c %c\n",op[1],op[2],op[3],op[4]);                           system("PAUSE");
     }
     if(c==0)
       return;
     
     op[c]='*';process(v,n,w/v[c],c-1);
     op[c]='+';process(v,n,w-v[c],c-1);
     op[c]='^';process(v,n,pow(w,1/v[c]),c-1);
}

But I don't memorize nothing because I don't know how to do it...
thanks for your help