[go: up one dir, main page]
Scribd
Upload
41 views4 pages

Steps To Dynamic Programming

Dynamic programming involves breaking problems down into stages with decisions made at each stage to determine the next state. The solution works backward from the last stage to the first to find the optimal solution at each stage. While greedy algorithms are usually more efficient, dynamic programming must be used when the optimal solution cannot be guaranteed through a greedy approach alone. Dynamic programming provides efficient solutions for problems where a brute force approach would be slow by showing the principle of optimality applies.

Uploaded by

MaimunaBegumKali
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
41 views4 pages

Steps To Dynamic Programming

Dynamic programming involves breaking problems down into stages with decisions made at each stage to determine the next state. The solution works backward from the last stage to the first to find the optimal solution at each stage. While greedy algorithms are usually more efficient, dynamic programming must be used when the optimal solution cannot be guaranteed through a greedy approach alone. Dynamic programming provides efficient solutions for problems where a brute force approach would be slow by showing the principle of optimality applies.

Uploaded by

MaimunaBegumKali
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 4

Steps to Dynamic Programming

Every problem is divided into stages


Each stage requires a decision
Decisions are made to determine the state of the
next stage
The solution procedure is to find an optimal
solution at each stage for every possible state
This solution procedure often starts at the last
stage and works its way forward
Greedy Approach VS Dynamic Programming (DP)

Greedy and Dynamic Programming are methods for


solving optimization problems.
Greedy algorithms are usually more efficient than DP
solutions.
However, often you need to use dynamic programming
since the optimal solution cannot be guaranteed by a
greedy algorithm.
DP provides efficient solutions for some problems for
which a brute force approach would be very slow.
To use Dynamic Programming we need only show that
the principle of optimality applies to the problem.

Greedy vs Dynamic 2
DP VS. Memoization

MCM can be solved by DP or Memoized


algorithm, both in O(n3).
Total (n2) subproblems, with O(n) for each.
If all subproblems must be solved at least
once, DP is better by a constant factor due to
no recursive involvement as in Memoized
algorithm.
If some subproblems may not need to be
solved, Memoized algorithm may be more
efficient, since it only solve these subproblems
which are definitely required.
3
DP Vs Divide and Conquer

Divide-&-conquer works best when all subproblems are


independent. So, pick partition that makes algorithm most efficient
& simply combine solutions to solve entire problem.
Dynamic programming is needed when subproblems are
dependent; we dont know where to partition the problem
Divide-&-conquer is best suited for the case when no
overlapping subproblems are encountered.
In dynamic programming algorithms, we typically solve each
subproblem only once and store their solutions. But this is at the
cost of space.

Greedy vs Dynamic 4

You might also like