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

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:



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.

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 19, 2024, from https://scienceaid.net/Dynamic_Programming

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

Chicago / Turabian ScienceAid.net. "Design and Algorythm of Dynamic Programming." Accessed Mar 19, 2024. 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.

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 32 times.

x

Thank Our Volunteer Authors.

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