algorithm - 动态编程-复杂性

我有一个家庭作业的问题，我已经想了一段时间了，我一辈子都想不出来。
我有一张X*Y尺寸的床单，还有一组较小尺寸的图案，价格与它们相关我可以水平或垂直切割板材，我必须找到优化的切割模式，才能从板材中获得最大的利润。
据我所知应该有（x*y）（x+y+模式）递归操作。复杂性被认为是指数的。有人能解释一下原因吗？
我提出的伪代码如下：

Optimize( w, h ) {
best_price = 0
    for(Pattern p :  all patterns) {
        if ( p fits into this piece of cloth && p’s price > best price) {best_price = p’s price}
    }
    for (i = 1…n){
       L= Optimize( i, h );
       R= Optimize( w-i, h);
       if (L_price + R_price > best_price) { update best_price}
    }
    for (i = 1…n){
        T= Optimize( w, i );
        B= Optimize( w, h-i);
        if (T_price + B_price > best_price) { update best_price}
    }
return best_price;
}

最佳答案

递归情况是指数型的，因为您可以在开始时选择将纸张剪切为0到最大宽度英寸或0到最大高度英寸，然后选择剪切剩余的部分（递归）。
这个问题听起来有点有趣，因为它涉及两个维度。
http://www.radford.edu/~nokie/classes/360/dp-rod-cutting.html
是个很好的向导。读这本书应该能让你走上正轨，而不必明目张胆地回答你的家庭作业。
当递归时为什么它是指数的相关部分：

This recursive algorithm uses the formula above and is slow
Code
    -- price array p, length n
    Cut-Rod(p, n)
        if n = 0 then
            return 0
        end if
        q := MinInt
        for i 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 to Cut-Rod(x, n), for any x
T(0)=0
T(n)=1+∑i=1nT(n−i)=1+∑j=0n−1T(j)
Solution: T(n)=2n