Understanding dynamic programming

To understand the dynamic programming better, we will walk through a very simple problem of climbing stairs. Consider we are at the bottom of a long staircase that has a n-step climb up to the top and we want to find, in how many genuinely distinct ways can we ascend, if at each move we take either one step or two steps.

The climbing stairs problem.

The brute force solution to the problem is to enumerate every possible climbing pattern. We list every sequence of one-step and two-step moves whose lengths add up to n, and count them to get the answer.

Enumerate all the distinct sequences of one and two steps that add up to n and count them.

However, this solution cannot be implemented as an algorithm as the number of such sequences grows exponentially with n (roughly like 1.618^n). And so, so for n = 200 the number of distinct sequences will have more than forty digits which is astronomical and not computer ever created can enumerate and then count these many sequences in the lifetime of the universe.

The number of distinct sequences grow exponentially with n.

A recursive formulation

Rather than enumerating every set of sequence upfront, we can try a recursive approach. We can focus on a single landing point and ask a simpler questions: how many distinct climbing patterns end exactly at step k? We can call this number f(k) ,and as we will see shortly, if we know the values of f(k) for every 1 <= k < n, we can answer to the original question, which will be f(n).