## Amazon Interview Question

SDE1s**Country:**India

**Interview Type:**In-Person

no, it seems to me that it is not fibonacci problem, it is a simple probability problem

for eg, for 3 = 3, using ur fiboinacci formula, it is giving answer as 3, but there are only 2 ways we can put tiles on a 2 * 3 floor.

the answer is (W/2) * 2 ways in total.

Please correct if my understanding of the question is wrong.

It's a dynamic programming question. And the solution format is just like the fabocci sequence. For example, if w = 1, then the answer is 1, if w = 2, the answer is 2, if w = 3, the answer is 1 + 2 = 3, if w = 4, the answer is 2 + 3 = 5. And the dynamic equation is

dp[n] = dp[n - 1] + dp[n - 2]. Here is the code:

- ravio June 07, 2014