### Anti-Frustration's blog

By Anti-Frustration, history, 5 weeks ago, ,

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

• -8

 » 5 weeks ago, # |   0 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
 » 5 weeks ago, # |   0 What do you mean by "solving top-down"?!
•  » » 5 weeks ago, # ^ |   0 For that you need to learn dp
•  » » 5 weeks ago, # ^ |   0 In this case, top-down means a function that is recursively called so that values are memoized in a dp structure.
 » 5 weeks ago, # |   0 Here is one implementation of top-down-dp for this problem int n, a, b, c; int dp(int n) { if (n < 0) return -1e9; if (n == 0) return 0; if (dp[n]) return dp[n]; return dp[n] = max({dp(n - a), dp(n - b), dp(n - c)}) + 1; } The complexity is $O(n)$ time & memory
 » 5 weeks ago, # | ← Rev. 12 →   +8 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: #include #include int n, a, b, c, dp[1 << 20]; inline int max(int x, int y) { return x > y ? x : y; } int DP(int i) { if(i < 0) return -0x3f3f3f3f; //if so, invalid if(dp[i] != 0 || i == 0) return dp[i]; return dp[i] = 1 + max(DP(i - a), max(DP(i - b), DP(i - c))); } int main() { scanf("%d%d%d%d", &n, &a, &b, &c); printf("%d\n", DP(n)); }