Unit 05
Dynamic Programming
, Dynamic Programming
Isa powerful design technique that can be used to
solve problems of a computational nature
Is typically applied to optimization problems
Dynamic Programming is an algorithm design
technique for optimization problems: often
minimizing or maximizing.
Like divide and conquer, DP solves problems by
combining solutions to subproblems.
2
, Dynamic Programming (DP) - CLRS
Dynamic programming (DP) applies when a problem has
both of these properties:
Optimal substructure: “optimal solutions to a problem
incorporate optimal solutions to related subproblems,
which we may solve independently”.
Overlapping subproblems: “a recursive algorithm
revisits the same problem repeatedly”.
Dynamic programming is typically used to:
Solve optimization problems that have the above
properties.
3
Dynamic Programming
, Dynamic Programming
Isa powerful design technique that can be used to
solve problems of a computational nature
Is typically applied to optimization problems
Dynamic Programming is an algorithm design
technique for optimization problems: often
minimizing or maximizing.
Like divide and conquer, DP solves problems by
combining solutions to subproblems.
2
, Dynamic Programming (DP) - CLRS
Dynamic programming (DP) applies when a problem has
both of these properties:
Optimal substructure: “optimal solutions to a problem
incorporate optimal solutions to related subproblems,
which we may solve independently”.
Overlapping subproblems: “a recursive algorithm
revisits the same problem repeatedly”.
Dynamic programming is typically used to:
Solve optimization problems that have the above
properties.
3
