Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

codeforces2k19's blog

By codeforces2k19, history, 9 months ago, In English,

I came across the solution to the problem:

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

ll fun(ll n)



    return INT_MIN;


    return 0;


    return dp[n];


return dp[n];


  • Vote: I like it
  • -3
  • Vote: I do not like it

9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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


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


. Since


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


must be the optimal solution for


(if there would be a better solution for


, 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$$$


$$$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.