Dynamic Programming or Memoization is a well known technique for optimization. It is just a method that remembers your previously calculated results and stores it somewhere so that when time comes you can use it again.
Just to begin with, a straightforward example of Memoization is calculation of Factorials. When we calculate Factorial of 5, i.e.
5! = 1*2*3*4*5 = 120
Now when you're asked to calculate Factorial of 6, a normal human being wouldn't go on like 1*2*3*4*5*6 rather he would think that "Well, I just calculated upto 5! why not simply multiply 6 to the answer of 5! " This is exactly what we are going to make our computers to do.
So, How do I make computer to remember pre-calculated results?
Answer is as simple as the question, just store them at a particular location in any array/list/vector.
Have a look at this simple Python implementation for memoized Factorial.
Just to begin with, a straightforward example of Memoization is calculation of Factorials. When we calculate Factorial of 5, i.e.
5! = 1*2*3*4*5 = 120
Now when you're asked to calculate Factorial of 6, a normal human being wouldn't go on like 1*2*3*4*5*6 rather he would think that "Well, I just calculated upto 5! why not simply multiply 6 to the answer of 5! " This is exactly what we are going to make our computers to do.
So, How do I make computer to remember pre-calculated results?
Answer is as simple as the question, just store them at a particular location in any array/list/vector.
Have a look at this simple Python implementation for memoized Factorial.
