Dynamic programming solves problems by combining the solutions to subproblems. It can be analogous to divide-and-conquer method, where problem is partitioned into disjoint subproblems, subproblems are recursively solved and then combined to find the solution of the original problem. In contrast, dynamic programming applies when the subproblems overlap - that is, when subproblems share subsubproblems. In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common subsubproblems. A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblems.
Let's look at an example. Italian Mathematician Leonardo Pisano Bigollo, whom we commonly know as Fibonacci, discovered a number series by considering the idealized growth of rabbit population. The series is:
1, 1, 2, 3, 5, 8, 13, 21, ......
We can notice that every number after the first two is the sum of the two preceding numbers. Now, let's formulate a function F(n) that will return us the nth Fibonacci number, that means,
F(n) = nth Fibonacci Number
So far, we've known that,
F(1) = 1 F(2) = 1 F(3) = F(2) + F(1) = 2 F(4) = F(3) + F(2) = 3
We can generalize it by:
F(1) = 1 F(2) = 1 F(n) = F(n-1) + F(n-2)
Now if we want to write it as a recursive function, we have
F(2) as our base case. So our Fibonacci Function would be:
Procedure F(n): //A function to return nth Fibonacci Number if n is equal to 1 Return 1 else if n is equal to 2 Return 1 end if Return F(n-1) + F(n-2)
Now if we call
F(6), it will call
F(4), which will call some more. Let's represent this graphically:
From the picture, we can see that
F(6) will call
F(5) will call
F(3). After calculating
F(5), we can surely say that all the functions that were called by
F(5) has been already calculated. That means, we have already calculated
F(4). But we are again calculating
F(6)'s right child indicates. Do we really need to recalculate? What we can do is, once we have calculated the value of
F(4), we'll store it in an array named dp, and will reuse it when needed. We'll initialize our dp array with -1(or any value that won't come in our calculation). Then we'll call F(6) where our modified F(n) will look like:
Procedure F(n): if n is equal to 1 Return 1 else if n is equal to 2 Return 1 else if dp[n] is not equal to -1 //That means we have already calculated dp[n] Return dp[n] else dp[n] = F(n-1) + F(n-2) Return dp[n] end if
We've done the same task as before, but with a simple optimization. That is, we've used memoization technique. At first, all the values of dp array will be -1. When
F(4) is called, we check if it is empty or not. If it stores -1, we will calculate its value and store it in dp. If it stores anything but -1, that means we've already calculated its value. So we'll simply return the value.
This simple optimization using memoization is called Dynamic Programming.
A problem can be solved using Dynamic Programming if it has some characteristics. These are:
F(4)can be divided into smaller subproblems
F(2). As the subproblems are similar to our main problem, these can be solved using same technique.
F(4)in common. This is the reason we stored the values in our array.
g(x). You know that the value of
g(z). Now if we can minimize
g(x)by minimizing both
g(z), only then we can say that the problem has optimal substructure. If
g(x)is minimized by only minimizing
g(y)and if minimizing or maximizing
g(z)doesn't have any effect on
g(x), then this problem doesn't have optimal substructure. In simple words, if optimal solution of a problem can be found from the optimal solution of its subproblem, then we can say the problem has optimal substructure property.