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.

Was this helpful? Yes | No | I need help

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

  1. 1
    Optimal structures.
    Advertisement
    Was this step helpful? Yes | No | I need help
  2. 2
    Overlapping-subproblems.
    Was this step helpful? Yes | No | I need help

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.

Was this helpful? Yes | No | I need help

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.
    Was this step helpful? Yes | No | I need help
  2. 2
    Top-Down approach.
    Was this step helpful? Yes | No | I need help
    Advertisement
Ad

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.

Was this helpful? Yes | No | I need help

Here is a quick example:

84.png

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

85.png

Level 1:

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

For example :

86.png

Then check for the numbers that end with 1.

0022X.png

Level 2:

87.png

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.

This article is part of a series on 'Design and Algorithm Analysis'. Read the full series here:

1) Design and Algorithm Analysis Overview

2) Algorithm Analysis

3) Algorithm Sorting

4) Algorithm Graph in Data Structure

5) Types and Styles of Algorithm Searchs

6) Types of Algorithm Laws

7) Dynamic_Programming

Referencing this Article

If you need to reference this article in your work, you can copy-paste the following depending on your required format:

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

MLA (Modern Language Association) "Design and Algorythm of Dynamic Programming." ScienceAid, scienceaid.net/Dynamic_Programming Accessed 25 Mar 2017.

Chicago / Turabian ScienceAid.net. "Design and Algorythm of Dynamic Programming." Accessed Mar 25, 2017. https://scienceaid.net/Dynamic_Programming.

If you have problems with any of the steps in this article, please ask a question for more help, or post in the comments section below.

Comments

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

Ask the author

TheGuyLoveNY
Featured Author
14 Articles Started
322 Article Edits
2,050 Points
TheGuyLoveNY is a featured author with ScienceAid. TheGuyLoveNY has achieved the level of "Private" with 2,050 points. TheGuyLoveNY has started 14 articles (including this one) and has also made 322 article edits. 300 people have read TheGuyLoveNY's article contributions.
TheGuyLoveNY's Message Board
TheGuyLoveNY: Hi, my name is TheGuyLoveNY.
TheGuyLoveNY: Can I help you with your problem about "Design and Algorythm of Dynamic Programming"?
 

Article Info

Categories : Design and Algorithm Analysis

Recent edits by: TheGuyLoveNY

Share this Article:

Thanks to all authors for creating a page that has been read 19 times.

Do you have a question not answered in this article?
Click here to ask one of the writers of this article
x

Thank Our Volunteer Authors.

Would you like to give back to the community by fixing a spelling mistake? Yes | No