Can cut ribbon problem : here is the problem be solved using top down and if it can , How ?

# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 200 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

4 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 179 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

Can cut ribbon problem : here is the problem be solved using top down and if it can , How ?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/07/2020 07:35:49 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

if DP[i] is the answer for i, we know that dp[i] = 1 + max(dp[i-a], dp[i-b], dp[i-c]). Now just work on the base cases and make sure i-a, i-b, and i-c, don't go out of bounds

What do you mean by "solving top-down"?!

For that you need to learn dp

In this case, top-down means a function that is recursively called so that values are memoized in a dp structure.

Here is one implementation of top-down-dp for this problem

The complexity is $$$O(n)$$$ time & memory

Every dynamic programming problem can be solved given a state, a transition, and an answer, so let's look for those here.

The simplest of these three factors to determine is what the answer should look like. It needs to be a number, the maximum number of ribbon pieces. But this needs to be specified over a given state. So what is the state?

Imagine the state as the length of the ribbon. This is because we can easily subproblem down to smaller states after cutting a certain number of pieces from the current ribbon. Call this length $$$i$$$. We need to find $$$\text{dp}[n]$$$.

Now, we need the transitions. Each transition can be viewed as making a cut. Since we can cut any lengths from $$$a$$$, $$$b$$$, $$$c$$$, we generate subproblems $$$\text{dp}[i-a]$$$, $$$\text{dp}[i-b]$$$, and $$$\text{dp}[i-c]$$$. Of course, in making the cut, we also get an extra ribbon piece. Then, if we solve the maximum for any of these three, we can get the original state. This gives us the below recurrence:

$$$\text{dp}[i] = 1 + \text{max}(\text{dp}[i-a], \text{dp}[i-b], \text{dp}[i-c])$$$

But what is the base case? Clearly, $$$\text{dp}[0] = 0$$$, since there are no pieces.

Now, given the state, transition, and answer, you can use recursion and memoization to design a top-down dp, starting from $$$\text{dp}[n]$$$ and moving downward.

I'll even put code here: