### codeforces2k19's blog

By codeforces2k19, history, 4 weeks ago, ,

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];

}

• -3

 » 4 weeks ago, # |   0 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.
•  » » 3 weeks ago, # ^ |   0 Thanks Sir!