CareerCup

I really like your idea. Here's the C++ implementation:

int tower(int n)
{
    if (n <= 0)
        return 0;

    switch (n) {
      case 1:     return 1;
      case 2:     return 2;
      case 3:     return 4;
      case 4:     return 8;
      default:    break;
    }

    n -= 4;

    queue<int> Q;
    Q.push(1);
    Q.push(2);
    Q.push(4);
    Q.push(8);

    int f = 1 + 2 + 4 + 8;
    while (--n) {
       Q.push(f);
       f = 2 * f -  Q.front();
       Q.pop();
    }

    return f;

}

In the expression f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4), how do we make sure that there are no overlapping sets between f(n-1) branch and f(n-2) branch and other branches. I think we will have overlapping sets. Just consider this scenario
In f(n-1), we have already selected a disk of height 1, now we select one disk of height 2 and all the remaining disks of height 1. We will effectively have one disk of height 2 and n-2 disks of height 1.
And in f(n-2), we have already selected a disk of height 2, and for remaining n-2 height we can select n-2 disks of height 1, so again we will end up with one disk of height 2 and n-2 disks of height 1.

Study fibonacci series.

Naive approach is straight recursion -> exponential runtime.
Improve this with DP down to linear.

But every DP solution also has a matrix multiplication method which is below linear (usually not expected in interview because you can't really code it conveniently in the languages we use in interviews).

I think I know what Fibonacci series is -- usually there is no "logic" behind the Fibonacci series, we are given what the series is and expected to code that using DP.

What I was asking is how someone might come up with the equation
f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4), n > 4

I know how to prove the equation -- I was curious about the thought process of coming up with that equation.

Do you know coin change problem ? The version where you have to return total number of ways to make change for some cost n.

Assume the coins are 1, 2, 3, 4.

It becomes this problem.


number of ways to make change for N is
= number of ways to use $1 and make change for remaining N-1
OR
number of ways to use $2 and make change for remaining N-2

...

etc.


Now you get recursive, then you use DP as optimization.

Aha!

So the number of ways we can construct a tower of height n (let's call it f(n)) is the sum of different ways we can construct a tower of height NOT using a particular brick of height h \in {1,2,3,4}: f(n) = \sum_{i=1}^{4} f(n-i).

Thanks!