Characterizing Dynamic Programming
R. Inkulu
http://www.iitg.ac.in/rinkulu/
(Characterizing Dynamic Programming)
1/5
Applicability
Brute-force algorithm is taking exponential time.
(Characterizing Dynamic Programming)
2/5
Applicability
Brute-force algorithm is taking exponential time.
Optimal substructure property: Any optimal solution to any subproblem
P of the given problem contains within it optimal solutions to
subproblems of P.
(Characterizing Dynamic Programming)
2/5
Applicability
Brute-force algorithm is taking exponential time.
Optimal substructure property: Any optimal solution to any subproblem
P of the given problem contains within it optimal solutions to
subproblems of P.
Overlapping subproblems: Two subproblems are said to overlap
whenever they are really the same subproblem but each occur as a
subproblem of a different problem.
(Characterizing Dynamic Programming)
2/5
Applicability
Brute-force algorithm is taking exponential time.
Optimal substructure property: Any optimal solution to any subproblem
P of the given problem contains within it optimal solutions to
subproblems of P.
Overlapping subproblems: Two subproblems are said to overlap
whenever they are really the same subproblem but each occur as a
subproblem of a different problem.
Independent subproblems: An optimal solution to a subproblem P can be
constructed from optimal solutions to subsubproblems of P while those
subsubproblems can be solved independent to each other.
(Characterizing Dynamic Programming)
2/5
Applicability
Brute-force algorithm is taking exponential time.
Optimal substructure property: Any optimal solution to any subproblem
P of the given problem contains within it optimal solutions to
subproblems of P.
Overlapping subproblems: Two subproblems are said to overlap
whenever they are really the same subproblem but each occur as a
subproblem of a different problem.
Independent subproblems: An optimal solution to a subproblem P can be
constructed from optimal solutions to subsubproblems of P while those
subsubproblems can be solved independent to each other.
Linear ordering property: The distinct subproblems that require to be
solved can be ordered from smallest to largest, with respect to their sizes.
(Characterizing Dynamic Programming)
2/5
Applicability
Brute-force algorithm is taking exponential time.
Optimal substructure property: Any optimal solution to any subproblem
P of the given problem contains within it optimal solutions to
subproblems of P.
Overlapping subproblems: Two subproblems are said to overlap
whenever they are really the same subproblem but each occur as a
subproblem of a different problem.
Independent subproblems: An optimal solution to a subproblem P can be
constructed from optimal solutions to subsubproblems of P while those
subsubproblems can be solved independent to each other.
Linear ordering property: The distinct subproblems that require to be
solved can be ordered from smallest to largest, with respect to their sizes.
The distinct subproblems that require to be solved are
(pseudo-)polynomial in number.
DP is a way of doing exhaustive search for an optimal solution without any
repetition of computations.
(Characterizing Dynamic Programming)
2/5
Applicability (cont)
Optimal substructure property is a requirement to both dynamic
programming as well as to greedy paradigms
(Characterizing Dynamic Programming)
3/5
Applicability (cont)
Optimal substructure property is a requirement to both dynamic
programming as well as to greedy paradigms
Independent subproblems is a requirement to dynamic programming and
divide-and-conquer
(Characterizing Dynamic Programming)
3/5
Applicability (cont)
Optimal substructure property is a requirement to both dynamic
programming as well as to greedy paradigms
Independent subproblems is a requirement to dynamic programming and
divide-and-conquer
Overlapping subproblems is unique to dynamic programming
(Characterizing Dynamic Programming)
3/5
Computing optimal solution vs optimal solution value
Formulate a DP recrurrence by exploiting the smallest-to-largest ordering of
subproblems together with the optimal substructure property and independent
subproblems.
(Characterizing Dynamic Programming)
4/5
Computing optimal solution vs optimal solution value
Formulate a DP recrurrence by exploiting the smallest-to-largest ordering of
subproblems together with the optimal substructure property and independent
subproblems.
Finding the optimum value v that corresponds to any optimal solution.
(Characterizing Dynamic Programming)
4/5
Computing optimal solution vs optimal solution value
Formulate a DP recrurrence by exploiting the smallest-to-largest ordering of
subproblems together with the optimal substructure property and independent
subproblems.
Finding the optimum value v that corresponds to any optimal solution.
Constructing an optimal solution O based on the optimal choices that we
have made while computing v.
(Characterizing Dynamic Programming)
4/5
Implmenting via memoization vs iteration
Avoid recomputations due to overlapping subproblems by maintaining a
tableu; accomplish this using either of -
(Characterizing Dynamic Programming)
5/5
Implmenting via memoization vs iteration
Avoid recomputations due to overlapping subproblems by maintaining a
tableu; accomplish this using either of Memoization over subproblems: top-down approach; natural extension
of recurrence equation (hence, recursive)
(Characterizing Dynamic Programming)
5/5
Implmenting via memoization vs iteration
Avoid recomputations due to overlapping subproblems by maintaining a
tableu; accomplish this using either of Memoization over subproblems: top-down approach; natural extension
of recurrence equation (hence, recursive)
Iteration over subproblems: subproblems are sorted by their size,
smallest first: bottom-up approach; simple; efficient due to lack of
recursive overheads; applicable when we can identify which
subproblems are important enough in computing v and/or O.
(Characterizing Dynamic Programming)
5/5
Implmenting via memoization vs iteration
Avoid recomputations due to overlapping subproblems by maintaining a
tableu; accomplish this using either of Memoization over subproblems: top-down approach; natural extension
of recurrence equation (hence, recursive)
Iteration over subproblems: subproblems are sorted by their size,
smallest first: bottom-up approach; simple; efficient due to lack of
recursive overheads; applicable when we can identify which
subproblems are important enough in computing v and/or O.
Further, based on the dependencies involved in filling any cell, we
choose the order in which to fill the cells.
(Characterizing Dynamic Programming)
5/5
