Dynamic programming builds solutions from solutions to simpler subproblems. It's closely allied to recursion, but dynamic programming algorithms are formulated as iteration usually over a very regular datastructure.

learn more… | top users | synonyms

8
votes
2answers
3k views

How to get better at solving Dynamic programming problems

I recently came across this question: "You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to parenthesize the ...
3
votes
2answers
2k views

How to prove a Dynamic programming strategy will work for an algorithm?

How can I prove that a dynamic programming (dp) strategy for a problem will work or not? For greedy algorithms, we can prove by showing the sub problems exhibits matroid property. Is there any such ...
3
votes
2answers
405 views

Help on a Dynamic Programming definition in Cormen

I am reading about Dynamic Programming from Cormen. In the beginning of the chapter it says (relating to the term Dynamic Programming): "Programming” in this context refers to a tabular method, ...
4
votes
4answers
463 views

Building a route creator

Ok, already up front, I'm going to tell you, that this is a bonus task for Data structure course I'm taking. That should take care of all the questions whether or not this is for a homework. Route ...
3
votes
1answer
2k views

How to apply dynamic programming to optimization problems with 2 constraints

Suppose you have a collection of blocks, each with a certain height and a certain weight. For example: Sample input: (190, 190) (120, 40) (100, 10) (90,130) (70, 40) (60, 70) (30, 30) (10, 90) ...
9
votes
2answers
2k views

How is the “Pizza picking problem‍​” solved using dynamic programming techniques?

Winkler's pizza picking problem: A circular pizza pie of n slices, where slice i has area S_i i.e, the area is different for each pie piece. Eaters Alice and Bob take turns picking slices, but it ...