I came across the solution to the problem:

http://codeforces.com/problemset/problem/189/A

can anyone explain me what is the approach to get this recursive relation(I am a beginner):

ll fun(ll n)

{

if(n<0) return INT_MIN; if(n==0) return 0; if(dp[n]!=-1) return dp[n]; dp[n]=max(fun(n-a)+1,max(fun(n-b)+1,fun(n-c)+1)); return dp[n];

}

Let $$$f(n)$$$ be the maximal number of ribbon pieces of length $$$a$$$, $$$b$$$, and $$$c$$$, so that their sum is $$$n$$$.

Let's assume that you know the solution. For instance the optimal way to cut a ribbon of length $$$n$$$ is

$$$abaacb$$$

. If you remove the last piece $$$b$$$, you end up with$$$abaac$$$

. Since$$$abaacb$$$

was the optimal solution for $$$n$$$,$$$abaac$$$

must be the optimal solution for$$$n-b$$$

(if there would be a better solution for$$$n-b$$$

, you can also improve the solution for $$$n$$$). This means that$$$f(n) = 1 + f(n-b)$$$

.Now back to the problem. Of course at the beginning you don't know the optimal solution. But you know that the last piece of the optima solution is $$$a$$$, $$$b$$$ or $$$c$$$. Therefore you can write

$$$f(n) = \max(1 + f(n-a), 1 + f(n-b), 1 + f(n-c))$$$

. If the optimal solution has a $$$b$$$ piece at the end,$$$1 + f(b)$$$

will be the biggest one.Now, to make a recursion stop, you need to define stop condition. Clearly

$$$f(0) = 0$$$

.And we want that

$$$f(n) = -\infty$$$

if you cannot cut the ribbon in such a way. E.g. if $$$n = 7$$$ and$$$a = 5, b = 6, c = 8$$$

, then you want that$$$f(n = 7) = -\infty$$$

. To accomplish this, you can just define$$$f(n) = -\infty$$$

if$$$n < 0$$$

. If it is not possible to cut the ribbon correctly, then you remove elements from the back and reach a negative number (doesn't matter how you remove them).To make this solution efficient, apply dynamic programming to it. In this code example they used Top-Down-DP.

Thanks Sir!