# Dynamic Programming Approach

when we are trying to solve a problem with dynamic programming. we have to follow some general steps

1. characterize the solution structure
2. Recursively define optimal solution
3. compute the value from bottom up fashion

Can anyone briefly explain the steps for this problem scenario. we need a 444 meter rope. but we have only small pieces of ropes. then we have to find out the minimum number of pieces of rope needs to construct that large rope.

Length---->Quantity

• 50m--->10
• 45m--->12
• 30m--->3
• 8m---->12
• 3m---->2
• 2m---->2
• In the guideline, you should also make sure that you store the sub-solutions appropriately. I think the more important thing is making sure you characterize the problem so that you don't end up doing brute force search. – InformedA Oct 8 '14 at 20:33
• Do you need exactly or at least 444 meters? – Yuval Filmus Oct 9 '14 at 1:10
• you just glue them, end-to-end, or do you lose some length for putting them together? - can you cut them? – babou Oct 9 '14 at 17:14
• need exactly 444 metres and we can't cut the ropes – Canon Oct 10 '14 at 5:36
• This is the subset sum problem. – Raphael Oct 10 '14 at 12:02