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

Popular posts from this blog

Team Work

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

Story about Samsara from Vidura in Maha Bharatha

From Sri Maha Bharatham - 11th Maha Parva (Stri Parva) - Jalapradanika Sub Parva - 5th Chapter "Dhritarashtra said, ‘Tell me in detail everything about the ways of that intelligence by which this wilderness of duties may be safely covered.’ "Vidura said, ‘Having bowed down to the Self-create, I will obey thy behest by telling thee how the great sages speak of the wilderness of life. A certain  brahmana,  living in the great world, found himself on one occasion in a large inaccessible forest teeming with beasts of prey. It abounded on every side with lions and other animals looking like elephants, all of which were engaged in roaring aloud. Such was the aspect of that forest that Yama himself would take fright at it. Beholding the forest, the heart of the  brahmana  became exceedingly agitated. His hair stood on end, and other signs of fear manifested themselves, O scorcher of foes! Entering it, he began to run hither and thither, casting his eyes on every point of