# Introduction

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 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.