Scribd
Upload
4 views1 page

Dynamic Programming

Dynamic programming is an optimization approach that breaks down problems into overlapping sub-problems, utilizing previously solved results to enhance efficiency. It contrasts with greedy algorithms by focusing on overall optimization rather than local solutions, and differs from divide and conquer by leveraging outputs from smaller sub-problems for larger ones. Common applications include the Fibonacci series, knapsack problem, and shortest path algorithms.

Uploaded by

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

Dynamic Programming

Dynamic programming is an optimization approach that breaks down problems into overlapping sub-problems, utilizing previously solved results to enhance efficiency. It contrasts with greedy algorithms by focusing on overall optimization rather than local solutions, and differs from divide and conquer by leveraging outputs from smaller sub-problems for larger ones. Common applications include the Fibonacci series, knapsack problem, and shortest path algorithms.

Uploaded by

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

DATA STRUCTURES - DYNAMIC PROGRAMMING

http://www.tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm Copyright © tutorialspoint.com

Dynamic programming approach is similar to divide and conquer in breaking down the problem in
smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-
problems are not solved independently. Rather, results of these smaller sub-problems are
remembered and used for similar or overlapping sub-problems.

Dynamic programming is used where we have problems which can be divided in similar sub-
problems, so that their results can be re-used. Mostly, these algorithms are used for optimization.
Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of
previously solved sub-problems. The solutions of sub-problems are combined in order to achieve
the best solution.

So we can say that −

The problem should be able to be divided in to smaller overlapping sub-problem.

The optimum solution can be achieved by using optimum solution of smaller sub-problems.

Dynamic algorithms use memoization.

Comparison
In contrast to greedy algorithms, where local optimization is addressed, dynamic algorithms are
motivated for overall optimization of the problem.

In contrast to divide and conquer algorithms, where solutions are combined to achieve overall
solution, dynamic algorithms uses the output of smaller sub-problem and then try to optimize
bigger sub-problem. Dynamic algorithms uses memoization to remember the output of already
solved sub-problems.

Example
The following computer problems can be solved using dynamic programming approach −

Fibonacci number series


Knapsack problem
Tower of Hanoi
All pair shortest path by Floyd-Warshall
Shortest path by Dijkstra
Project scheduling

Dynamic programming can be used in both top-down and bottom-up manner. And ofcourse, most
of the times, referring to previous solution output is cheaper than re-computing in terms of CPU
cycles.

You might also like