algorithm - Dynamic Programing- complexity -

i have homework problem have been trying figure out time now, , can't figure out life of me.

i have sheet of size x*y, , set of patterns of lesser sizes, price values associated them. can cut sheet either horizontally or vertically, , have find optimized cutting pattern greatest profit sheet.

as far can tell there should (x*y)(x+y+#ofpatterns) recursive operations. complexity supposed exponential. can please explain why?

the pseudo-code have come follows:

optimize( w, h ) { best_price = 0     for(pattern p :  patterns) {         if ( p fits piece of cloth && p’s price > best price) {best_price = p’s price}     }     (i = 1…n){        l= optimize( i, h );        r= optimize( w-i, h);        if (l_price + r_price > best_price) { update best_price}     }     (i = 1…n){         t= optimize( w, );         b= optimize( w, h-i);         if (t_price + b_price > best_price) { update best_price}     } return best_price; } 

the recursive case exponential because can @ start choose cut paper 0 max width inches or 0 max height inches , optionally cut remaining pieces (recurse).

this problem sounds bit more interesting case of rod cutting problem since involves 2 dimensions.

http://www.radford.edu/~nokie/classes/360/dp-rod-cutting.html

is guide. read should put on right track without blatantly answering homework.

the relevant portion why exponential when recursing:

this recursive algorithm uses formula above , slow code     -- price array p, length n     cut-rod(p, n)         if n = 0             return 0         end if         q := minint         in 1 .. n loop             q = max(q, p(i) + cut-rod(p, n-i)         end loop         return q  recursion tree (shows subproblems): 4/[3,2,1,0]//[2,1,0],[1,0],0//[1,0],0,0//0 performance: let t(n) = number of calls cut-rod(x, n), x t(0)=0 t(n)=1+∑i=1nt(n−i)=1+∑j=0n−1t(j) solution: t(n)=2n