This week, to prepare for the summer school in Bioinformatics, I’m learning dynamic programming, a “divide-and-conquer” style of algorithms. The idea of this technique seems quite simple: we solve the problem by solving its subproblems. We can think of the Fibonacci problem as a simple illustration: the value of the nth component is the sum of its 2 precedent neighbors. However, the dynamic programming problems usually come in different shapes, and it takes me a lot of time to wrap my head around its idea, let alone applying it to find the solution for the programming challenge on Rosalind.
Basically, the principle of dynamic programming is : memoize (remember) and re-use the solutions. The biggest challenge with dynamic programming is to determine the subproblems. There are 2 main techniques to solve a dynamic problems: top-down and bottom-up.
Back to the Fibonacci sequence. Today on Rosalind, I encounter a modified version of this classical example. Fibonacci sequence came from an attempt of calculating the reproduction of a population of rabbits.
In the classical version, we don’t take into account the rabbit mortality rate, which means that once the rabbits reach their breeding age, they will keep breeding and never die.
To make it more realistic, the Rosalind challenge add one more detail: the rabbits will die after n months:
This makes the problem more complicated, and here is my solution:
My idea is to keep track of the population of every generation in a list and update it through each month. The number of rabbits will be then the sum of this list. However I don’t think that this solution is “dynamic programming”: there is no memoization and no re-use of solution (or is there ?!). Anyway, this is the only solution that I could come up with, I’ll update this post if I find a true “dynamic programming” solution …
Updated: I found this solution on the Rosalind page. The idea is the same as mine but it’s so elegant and it shows us the beauty of Python !