dynamic-programming Getting started with dynamic-programming Introduction To Dynamic Programming

Example

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(1) and 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(5) and 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) and F(4). Now F(5) will call F(4) and 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(4) as 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[4]. 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:

• Subproblems:
  A DP problem can be divided into one or more subproblems. For example: F(4) can be divided into smaller subproblems F(3) and F(2). As the subproblems are similar to our main problem, these can be solved using same technique.
• Overlapping Subproblems:
  A DP problem must have overlapping subproblems. That means there must be some common part for which same function is called more than once. For example: F(5) and F(6) has F(3) and F(4) in common. This is the reason we stored the values in our array.

• Optimal Substructure:
  Let's say you are asked to minimize the function g(x). You know that the value of g(x) depends on g(y) and g(z). Now if we can minimize g(x) by minimizing both g(y) and 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.