The most difficult part about solving dynamic programming algorithms is constructing the table. The table is essentially analogous to the stack from of a recursive algorithm, each cell of the table stores the answers to those problems.
Topics of Discussion
What is the Bird-Friend Algorithm? What is an Instance? What is the Bird Question? What are Sub-Instances? What is this Table? Construct Solutions? How do we Construct this Table? How do we actually code this?
What is the Bird-Friend Algorithm Really?
The idea here is simple to loop over all possible solutions. The bird-friend algorithm gives a nice story to place the algorithm to that can be recited every time this problem needs to be solved. It consists of making the best decision for each instance by asking a bird a question, then asking a friend to solve the sub-instance consistent with that bird answer, and storing it in a table.
What is an Instance?
The instance is usually an optimization problem, more specifically when you’re trying to optimize something subject to another parameter. Some examples of these types of problems are: Searching a Graph for the Best Path, The Knapsack Problem, Weighted event scheduling, and the Stock Algorithm.
What is the Bird Question?
The bird question is just a simple question that you ask the bird about the end of the instance. Don’t be afraid to ask your bird more than one question! Be conscious of how many answers to the questions you ask exist. You can think of the bird question of how can I know how to get back on track. i.e. what question do you wish your lost son would ask. Some typical bird questions consist of do I take the last element or not? Do I take the path or not? After determining what your questions could be, think about possible answers to each question.
What are Sub-Instances?
A sub-instance is a smaller instance to the problem. Like with recursive algorithms we give our “friends” a smaller instance that meets the precondition. With dynamic programming algorithms we also do this. The smaller instance to the problem will be the same instance without the bird answer.
What is the Table?
In the bird-friend algorithm we further extract this table into instances and birds advice. The instances can be thought of as nodes on a graph. The birds advice is what the inner loop is doing, solving the local problem. This table is the optimal solution consistent with the current bird answer. i.e. table[Instances][birds advice] stores the optimal solution for each instance consistent with that particular bird answer.
How do we Construct this Table?
To construct this table we need to come up with a solution for every instance consistent with each bird answer, compare them and store the best one in the table; for later consideration.