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

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

Online 2 Year MS Software Systems (MSSS) Program from Bits Pilani

BITS is offering an online (not classroom) 2 Year MS Software Systems (MSSS) Program. Whoever interested can go through this link: http://www.bits-pilani.ac.in/dlp-home/Admissions/12008/advertisement.html You can contact: George Daleep ( George_Daleep@satyam.com ; 09959188837) Santha_Oommen ( santha_oommen@satyam.com ; 09849427215) More Info From Bits Advertisement: Since we have received a number of queries from associates on the MS program from BITS Pilani, we would like to clarify matters. BITS is offering an online (not classroom) 2 Year MS Software Systems (MSSS) Program provided you meet conditions. Some basic information about eligibility, requirements and fees is given below: Eligibility Criteria: First Class BE / MSc / MCA / MBA / BITS BS (Minimum 60% aggregate) or equivalent degree and at least 12 months of relevant post-qualification experience. Candidates with 3-year BSc, BCA, BBA, BCS, BIT etc are NOT eligible. Additional (M

Your mind can be your best asset or your worst enemy. Train it well.

Your mind can be your best asset or your worst enemy. Train it well.