Anti-Frustration's blog

By Anti-Frustration, history, 4 years ago, In English

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

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

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
Rev. 12   Vote: I like it +8 Vote: I do not like it

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 <stdio.h>
#include <string.h>

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)); 
}