# Design and Algorythm of Dynamic Programming

Edited by TheGuyLoveNY, Jen Moreau

## Dynamic Programming:

Dynamic programming is an approach to solving problems, In which problems are broken into smaller problems, i.e subproblems. Much like Divide and conquer approach but In dynamic programming, Not only we divide the problem into a smaller set and solve those subproblems but we also store the result of these different subproblems. So whenever in future we do not have to recompute the same problem, Instead just retrieve back previously solved problems (which are stored in memory data structures). Dynamic programming is often used for optimization. Since dynamic programming keeps track of all the previously encountered problems and figures out the optimal (efficient) solution.

There is two main aspect for a problem to be solved by dynamic programming:

1. 1
Optimal structures.
2. 2
Overlapping-subproblems.

If a problem can be solved by breaking it into subproblems and then merging them to a single piece of the solution then such problem is referred as optimal structures. Merge sort and Quicksort follows this approach and hence are not considered as dynamic programming.

Overlapping-subproblems refers to the small subproblems that can be recursively solved and will not generate any new problem. Algorithms like Bellman-Ford, Floyd-Warshall falls under this category.

Techniques that are used in dynamic programming are mainly:

• Tabulation.
• Memorization.

Dynamic programming can be achieved using two ways:

1. 1
Bottom-Up approach.
2. 2
Top-Down approach.

## Hashing:

Hashing is the process of searching a variable from computer memory. Hashing searches for the key stored in a hash table with the help a hash function. Hashing is one of the fastest searching techniques. Hashing uses the most basic Binary search.

Here is a quick example:

First, put them on the hash table according to their values:

Level 1:

Check whether any number in the list ends with digit 0 (none in our case).

For example :

Then check for the numbers that end with 1.

Level 2:

There is no buffer overflow. Hence, We can stop hashing. If there would have been any buffer overflow, we would have proceeded to next level, i.e Level 3.

APA (American Psychological Association)
Design and Algorythm of Dynamic Programming. (2017). In ScienceAid. Retrieved Apr 24, 2018, from https://scienceaid.net/Dynamic_Programming

MLA (Modern Language Association) "Design and Algorythm of Dynamic Programming." ScienceAid, scienceaid.net/Dynamic_Programming Accessed 24 Apr 2018.

Chicago / Turabian ScienceAid.net. "Design and Algorythm of Dynamic Programming." Accessed Apr 24, 2018. https://scienceaid.net/Dynamic_Programming.

ScienceAid welcomes all comments. If you do not want to be anonymous, register or log in. It is free.

## Article Info

Categories : Design and Algorithm Analysis

Recent edits by: TheGuyLoveNY