Find the maximum number of pieces a rod can be cut

Question

Here is the complete problem statement:

Given a rope of length n, you need to find the maximum number of pieces
you can make such that the length of every piece is in set {a, b, c} for
the given three values a, b, c

I know that the optimal solution can be achieved through Dynamic Programming, however, I have not learned that topic yet and I need to solve this problem recursively. With recursion, the main thing is to identify a subproblem and that's what I'm mainly having difficulty with doing. Can anyone give me an intuitive way to think of this problem? Sort of like a higher level description of the recursion if that makes sense. Is there an easier problem similar to this that I can try first that would help me solve this?

Thanks in advance.

Answer 1

It's already quite simple, with recursion we can just check all posibilities, in one step we can either cut away a piece of length a, b, or c so from problem of size n we get sup-problem of smaller size n-x

Of course we need a base case, so when n=0 we have succeeded so we can return 0, in case of n < 0 we have failed so we can return some negative infinity constant

Sample pseudo-code:

int solve(int n){
    if(n < 0) return -123456789; //-Infinity
    if(n == 0) return 0;
    return 1 + max(solve(n-a), solve(n-b), solve(n-c));
}

going to dynamic programming is as simple as setting up memo lookup table

int solve(int n){
    if(n < 0) return -123456789; //-Infinity
    if(n == 0) return 0;
    if(n in memo)return memo[n]
    return memo[n] = 1 + max(solve(n-a), solve(n-b), solve(n-c));
}