BDIOI -2013/7
Posted: Tue Feb 25, 2014 5:06 pm
Find of the value of $$F(n,k)$$
$$F(n,k) = 2F(n-1,k) + F(n-1,k-1)$$ where, $$F(0,k) = 1$$, $$F(n,0) = 1$$
$$F(n,k) = 2F(n-1,k) + F(n-1,k-1)$$ where, $$F(0,k) = 1$$, $$F(n,0) = 1$$
Hi Fatin.
Could you clarify which competition you are referring to by BDIOI? Is it BdOI?
If I guessed right, then, just so that you know, there's a sub-forum in this very forum for Informatics Olympiad problems.
(Look for IOI and Computer Science subforums in the home page)
In any case, memorization (Dynamic programming) is a good approach to this problem.
You can either write the pseudocode or just simulate the whole process in your answer script to get the answer of this problem.
Any of the two will secure you full marks.
For dynamic programming basics, see this article.
Brute force, though time consuming, are also useful techniques to solve this problem.