Skip to main content

Dynamic Programming

Those who do not remember the past are condemned to repeat it. ~ George Santayana

In terms of mathematical optimization, dynamic programming usually refers to simplifying a decision by breaking it down into a sequence of decision steps over time.

Dynamic programming amounts to breaking down an optimization problem into simpler sub-problems, and storing the solution to each sub-problem so that each sub-problem is only solved once.

Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler sub-problems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its sub-problems.

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems.

If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead. This is why merge sort and quick sort are not classified as dynamic programming problems.

Some good resources to learn about dynamic programming:
  1. Demystifying Dynamic Programming
  2. Dynamic Programming – 7 Steps to Solve any DP Interview Problem
  3. Topcoder - Dynamic Programming from Novice to Advanced


Comments

Post a Comment

Popular posts from this blog

Team Work

5 comments
Read more

Ramo Vigrahavan Dharmah

A great verse from Ramayana: आहार निद्रा भय मैथुनं च  सामान्यमेतत् पशुभिर्नराणाम् । धर्मो हि तेषामधिको विशेष:  धर्मेण हीनाः पशुभिः समानाः ॥ AhAra-nidrA-bhaya-maithunam cha samAnam_etat_pashubhir_narANAm | dharmo hi teShAm adhiko visheSho dharmeNa hInAH pashubhiH samAnAH|| Eating, Sleep, Fear and Sex ; these habits are common between human beings and animals. It is the Dharma which is the special quality of the human beings. Without the Dharma, they are similar to the animals.  Rama is The Embodiment Of Dharma.  Maaricha, while speaking to Ravana- (Aranya Kandam 37-13): रामो विग्रहवान् धर्मः साधुः सत्य पराक्रमः | राजा सर्वस्य लोकस्य देवानाम् इव वासवः || ३-३७-१३|| raamo vigrahavaan dharmaH saadhuH satya paraakramaH | raajaa sarvasya lokasya devaanaam iva vaasavaH || 3-37-13 "Rama is the embodiment of righteousness, he is an equable person with truthfulness as his valour, and as with Indra to all gods he is the king of entire world. [3-37-13] Another great phra
Post a Comment
Read more

Microsoft moving to Live (Online sofware services)

Microsoft plans to launch Internet-based complements to its core products(Windows and Office), that create opportunities for the company to sell online subscriptions and advertising. Windows Live is a set of Internet-based personal services, such as e-mail, blogging and instant messaging. Office Live will come in both ad-based and subscription versions that augment MS' Office suite. The programs won't replace the paid software but instead seem aimed at capturing its online share. Windows Live at Live.com . From BBC The move to online software services is closely linked to the spread of high-speed access to the internet, as online software services are only as good as a user's access to the web. Mr Gates, who is Microsoft's chairman and chief software architect, said the strategic shift would change his company's approach to doing business: "We are trying to put a 'service plus software' mentality into many of the product groups inside Microsoft."
Post a Comment
Read more