Recursive solution to Dynamic Programming [duplicate]

Question

Possible Duplicate:
Dynamic Programming and Knapsack Application

I have been trying to understand Dynamic Programming but with each new problem I get a bit confused over how to write recursion for it.

Take the following problem: There is an L × H metal sheet which can be cut by a machine into two pieces either vertically or horizontally.Both L, H are integral and the cuts also happen along integral values.There are n rectangular patterns l(i) × h(i) , i ≤ n (l , h are also integral) where the i-th pattern has profit c(i). Design an efficient algorithm to cut the sheet in a way so as to maximize the total profit.

Now I think for solving it we would create a table of LxH (which would be filled diaganally). But how do we form a recursion for solving this problem ?

Answer 1

I'd try something like for every T(L, H), verify the best alternative between:

• collect the profit right away
• cut every possible way horizontally
• cut every possible way vertically

Something like:

T(L, H) = max(
    c(L, H),  
    T(i, H)+T(L-i, H), // 0<i<L
    T(L, i)+T(L, H-i)  // 0<i<H
)