Skip to main content

What is Dynamic Programming ?

 




  • What actually dynamic programming is ?

In computer science or mathematics, dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. Also known as dynamic optimization.

Dynamic programming is similar to divide and conquer only difference is that dynamic programming is used when there is overlapping subproblem property and in divide and conquer there is no overlapping subproblem property.

example, fibonacci series.

When to use dynamic programming ?

Following two attributes suggests that a problem can be solved using dynamic programming :

  1. optimal substructure
  2. overlapping sub-problems.
  • Ways to of using dynamic programming :
  1. Top-Down : Firstly, Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization.
  2. Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Tabulation.
Labels:

Comments

Post a Comment

Popular posts from this blog

Need of Open Source ?

You have already got what is  Open Source  from previous blogs. The simple reason is that why to pay if we get is free. Lets take an example you spend lots of money to buy an windows genuine some of the people don’t buy the licence copy of it but they buy an creak (DOS) version of windows but they have some problem in it. Some what same not a completely different OS are freely available in market then why should we pay for it ? You get high quality of software and hardware also in open source. They are very powerful and smooth running no lags get while working.They also give full support to solve your problem.Think an example of google you search on google and you get the result of what you search if google say that I want money for every search results then ?you will pay for it ? That the need of  open source .
Post a Comment
Read more

The End Is near: January 19, 2038 3:14:07 GMT

  Year 2038 problem The Year 2038 problem is an issue for computing and data storage situations in which time values are stored or calculated as a signed 32-bit integer, and the number is interpreted as the number of seconds since 00:00:00 UTC on 1 January 1970 (the epoch). Systems working on 32-bit cannot encode times after 03:14:07 UTC on 19 January 2038, analogous to the Y2K problem , in which 2-digit values representing the number of years since 1900 could not encode the year 2000 or later. Most 32-bit Unix like systems store and manipulate time in this Unix time format, so the year 2038 problem is sometimes referred to as the  Unix Millennium  Bug by association. What is Unix time? The  Unix epoch   time  is the number of seconds that have elapsed since January 1, 1970 (midnight UTC/GMT), not counting leap seconds . Literally speaking the epoch is Unix time 0 (midnight 1/1/1970), but ‘epoch’ is often used as a synonym for ‘Unix time’. Many Unix systems...
Post a Comment
Read more