Dynamic programming is a clever methodology used for solving very complex problems.
The basic idea is like construction works: you build a bigger wall by placing new bricks on existing ones. In dynamic programming, you identify a new solution by extending a previous one. Divide et impera to its best.
In the fields of bioinformatics and computational biology, two great examples of dynamic programming are used: alignment algorithms and Hidden Markov Models. I’m going to present some of them in the next posts, for now I would like to focus on the basic idea of dynamic programming, by using a very simple example.
At the basic of alignment and HMM algorithms you have a table. What you have to do is filling the table using some rules: you start from one side of the table, apply the rules to the next row or column and keep going on until the table is filled.
Let’s try the following: create a table of 5 rows and 10 columns.
As first step, you should always fill at leas a value into the table (initialization step). In our example, we put the numbers from 1 to 5 into the first column.
Now it is time to apply the iterative step: we have to repeat the same operation on all cells, starting from one side of the table and moving on.
In our example, the cell should contain the result of the following formula: value on the left times row number.
The first row should read as 1,1,1,1,1; the second 2,4,8,16,32 and so on. As you can see, each row contains the powers of the first number. What you needed to build it was just a local information: the previous value. So the 16 in the second row comes from the 8 in the third column, while the 16 in the fourth row is evaluated from the 4 on its left.
This is a very simple example, real dynamic programming algorithms may use the whole preceding column, complex mathematical functions on the previous values and so on. But the strategy is the same: if I change my function to “The maximum value on the preceding column times the minimum one, minus row number”, I would proceed in the same way: filling one column at the time, just using a different function.