3 Better format edited Apr 8 '16 at 15:34 jonaprieto 1,34622 gold badges1212 silver badges2222 bronze badges Your problem is a classic one (a variant of the knapsack problem). Maybe is more clear to you, if you see explicitly the overlapping into subproblems, something necessary to apply the dynamic programing paradigm, after then, is natural come up with the recursion relation. For example, when you have the rod of length $$n$$, you can cut it in so many ways, like cut in $$1$$ or $$2$$, thats it, ending with a rod of lengths $$[1$$ and $$n-1]$$ or $$[2$$ and $$n-2]$$, respectively. In each case, you find the maximum profit and the compare with the other options, as we expect. $$l(n):=\text{ maximun profit of cutting the rod of length n in all possible ways }.$$ For instance, in the first case, we need the solution for the second one, because cut in $$1$$ (i.e. $$[1$$ and $$n-1]$$) means $$\text{price}(1)+l(n-1)$$, where $$l$$ is the method that solves our problem for a rod of length $$n$$. But solves $$l(n-1)$$ should consider cut in $$1$$ again, but this time in a length of $$n-2$$, that is, $$\text{price}(1) +l(n-2)$$. As we can see $$l(1)$$ was already required, and if we continue, it will be required again. Also, it repeats with $$l(n-2)$$ and others, overlapping subproblems. $$l(n):=\text{ maximun profit of cutting the rod of length n in all possible ways },$$ $$l(n)=\max \{\ \underbrace{\text{price}(1)+ \color{blue}{l(n-1)}}_{\text{cut in } 1},\ \text{price}(2) + \color{red}{l(n-2)}, \text{price}(3) + \color{green}{l(n-3)}, \cdots,\underbrace{\text{price}(n-1) + l(1)}_{\text{cut in }n-1} \}.$$ $$l(n)=\max \{\ \underbrace{\color{blue}{\text{price}(1)}+ l(n-1)}_{\text{cut in } 1},\ \text{price}(2) + l(n-2), \cdots, \underbrace{\text{price}(n-2) + l(2)}_{\text{cut in }n-2},\ \text{price}(n-1) + \color{blue}{l(1)}\ \}.$$ And, $$\color{blue}{l(n-1)}=\max \{\ \underbrace{\text{price}(1)+ \color{red}{l(n-2)}}_{\text{cut in } 1},\ \text{price}(2) + \color{green}{l(n-3)}, \cdots, \text{price}(n-3) + l(2) \}.$$ Therefore, $$l(n) = \max_{i=1,\cdots,n-1} \text{price}(i) + l(n-i).$$ with $$l(0) = 0$$. Why is $$O(n^2)$$? Why is $$O(n^2)$$? To build up the solution $$l(n)$$, we have to compute the small instances of the problem, $$l(1), l(2),\cdots, l(n-1)$$. In each case, we have to iterate all possible cuts $$1, 2, \cdots, n - 1$$. Then, we have $$O(n)\cdot O(n)$$ running time. Your problem is a classic one (a variant of the knapsack problem). Maybe is more clear to you, if you see explicitly the overlapping into subproblems, something necessary to apply the dynamic programing paradigm, after then, is natural come up with the recursion relation. For example, when you have the rod of length $$n$$, you can cut it in so many ways, like cut in $$1$$ or $$2$$, thats it, ending with a rod of lengths $$[1$$ and $$n-1]$$ or $$[2$$ and $$n-2]$$, respectively. In each case, you find the maximum profit and the compare with the other options, as we expect. For instance, in the first case, we need the solution for the second one, because cut in $$1$$ (i.e. $$[1$$ and $$n-1]$$) means $$\text{price}(1)+l(n-1)$$, where $$l$$ is the method that solves our problem for a rod of length $$n$$. But solves $$l(n-1)$$ should consider cut in $$1$$ again, but this time in a length of $$n-2$$, that is, $$\text{price}(1) +l(n-2)$$. As we can see $$l(1)$$ was already required, and if we continue, it will be required again. Also, it repeats with $$l(n-2)$$ and others, overlapping subproblems. $$l(n):=\text{ maximun profit of cutting the rod of length n in all possible ways },$$ $$l(n)=\max \{\ \underbrace{\color{blue}{\text{price}(1)}+ l(n-1)}_{\text{cut in } 1},\ \text{price}(2) + l(n-2), \cdots, \underbrace{\text{price}(n-2) + l(2)}_{\text{cut in }n-2},\ \text{price}(n-1) + \color{blue}{l(1)}\ \}.$$ Therefore, $$l(n) = \max_{i=1,\cdots,n-1} \text{price}(i) + l(n-i).$$ Why is $$O(n^2)$$? To build up the solution $$l(n)$$, we have to compute the small instances of the problem, $$l(1), l(2),\cdots, l(n-1)$$. In each case, we have to iterate all possible cuts $$1, 2, \cdots, n - 1$$. Then, we have $$O(n)\cdot O(n)$$ running time. Your problem is a classic one (a variant of the knapsack problem). Maybe is more clear to you, if you see explicitly the overlapping into subproblems, something necessary to apply the dynamic programing paradigm, after then, is natural come up with the recursion relation. For example, when you have the rod of length $$n$$, you can cut it in so many ways, like cut in $$1$$ or $$2$$, thats it, ending with a rod of lengths $$[1$$ and $$n-1]$$ or $$[2$$ and $$n-2]$$, respectively. In each case, you find the maximum profit and the compare with the other options, as we expect. $$l(n):=\text{ maximun profit of cutting the rod of length n in all possible ways }.$$ For instance, in the first case, we need the solution for the second one, because cut in $$1$$ (i.e. $$[1$$ and $$n-1]$$) means $$\text{price}(1)+l(n-1)$$, where $$l$$ is the method that solves our problem for a rod of length $$n$$. But solves $$l(n-1)$$ should consider cut in $$1$$ again, but this time in a length of $$n-2$$, that is, $$\text{price}(1) +l(n-2)$$. As we can see $$l(1)$$ was already required, and if we continue, it will be required again. Also, it repeats with $$l(n-2)$$ and others, overlapping subproblems. $$l(n)=\max \{\ \underbrace{\text{price}(1)+ \color{blue}{l(n-1)}}_{\text{cut in } 1},\ \text{price}(2) + \color{red}{l(n-2)}, \text{price}(3) + \color{green}{l(n-3)}, \cdots,\underbrace{\text{price}(n-1) + l(1)}_{\text{cut in }n-1} \}.$$ And, $$\color{blue}{l(n-1)}=\max \{\ \underbrace{\text{price}(1)+ \color{red}{l(n-2)}}_{\text{cut in } 1},\ \text{price}(2) + \color{green}{l(n-3)}, \cdots, \text{price}(n-3) + l(2) \}.$$ Therefore, $$l(n) = \max_{i=1,\cdots,n-1} \text{price}(i) + l(n-i).$$ with $$l(0) = 0$$. Why is $$O(n^2)$$? To build up the solution $$l(n)$$, we have to compute the small instances of the problem, $$l(1), l(2),\cdots, l(n-1)$$. In each case, we have to iterate all possible cuts $$1, 2, \cdots, n - 1$$. Then, we have $$O(n)\cdot O(n)$$ running time. 2 I missed the description of the problem. edited Apr 8 '16 at 15:23 jonaprieto 1,34622 gold badges1212 silver badges2222 bronze badges Your problem is a classic one (a variant of the knapsack problem). Maybe is more clear to you, if you see explicitly the overlapping into subproblems, something necessary to apply the dynamic programing paradigm, after then, is natural come up with the recursion relation. For example, when you have the rod of length $$n$$, you can cut it in so many ways, like cut in $$1$$ or $$2$$, thats it, ending with a rod of lengths $$[1$$ and $$n-1]$$ or $$[2$$ and $$n-2]$$, respectively. In each case, you find the maximum profit and the compare with the other options, as we expect. For instance, in the first case, we need the solution for the second one, because cut in $$1$$ (i.e. $$[1$$ and $$n-1]$$) means $$l(1)+l(n-1)$$$$\text{price}(1)+l(n-1)$$, where $$l$$ is the method that solves our problem for a rod of length $$n$$. But solves $$l(n-1)$$ should consider cut in $$1$$ again, but this time in a length of $$n-2$$, that is, $$l(1) +l(n-2)$$$$\text{price}(1) +l(n-2)$$. As we can see $$l(1)$$ was already required, and if we continue, it will be required again. Also, it repeats with $$l(n-2)$$ and others, overlapping subproblems. $$l(n):=\text{ maximun profit of cutting the rod of length n in all possible ways },$$ $$l(n)=\max \{\ \underbrace{\color{blue}{l(1)}+ l(n-1)}_{\text{cut in } 1},\ l(2) + \color{red}{l(n-2)}, \cdots, \underbrace{\color{red}{l(n-2)} + l(2)}_{\text{cut in }n-2},\ l(n-1) + \color{blue}{l(1)}\ \}.$$$$l(n)=\max \{\ \underbrace{\color{blue}{\text{price}(1)}+ l(n-1)}_{\text{cut in } 1},\ \text{price}(2) + l(n-2), \cdots, \underbrace{\text{price}(n-2) + l(2)}_{\text{cut in }n-2},\ \text{price}(n-1) + \color{blue}{l(1)}\ \}.$$ Therefore, $$l(n) = \max_{i=1,\cdots,\lfloor \frac{n-1}{2}\rfloor} l(i) + l(n-i).$$$$l(n) = \max_{i=1,\cdots,n-1} \text{price}(i) + l(n-i).$$ Why is $$O(n^2)$$? To build up the solution $$l(n)$$, we have to compute the small instances of the problem, $$l(1), l(2),\cdots, l(n-1)$$. In each case, we have to iterate all possible cuts $$1, 2, \cdots, n - 1$$. Then, we have $$O(n)\cdot O(n)$$ running time. Your problem is a classic one (a variant of the knapsack problem). Maybe is more clear to you, if you see explicitly the overlapping into subproblems, something necessary to apply the dynamic programing paradigm, after then, is natural come up with the recursion relation. For example, when you have the rod of length $$n$$, you can cut it in so many ways, like cut in $$1$$ or $$2$$, thats it, ending with a rod of lengths $$[1$$ and $$n-1]$$ or $$[2$$ and $$n-2]$$, respectively. In each case, you find the maximum profit and the compare with the other options, as we expect. For instance, in the first case, we need the solution for the second one, because cut in $$1$$ (i.e. $$[1$$ and $$n-1]$$) means $$l(1)+l(n-1)$$, where $$l$$ is the method that solves our problem for a rod of length $$n$$. But solves $$l(n-1)$$ should consider cut in $$1$$ again, but this time in a length of $$n-2$$, that is, $$l(1) +l(n-2)$$. As we can see $$l(1)$$ was already required, and if we continue, it will be required again. Also, it repeats with $$l(n-2)$$ and others, overlapping subproblems. $$l(n):=\text{ maximun profit of cutting the rod of length n in all possible ways },$$ $$l(n)=\max \{\ \underbrace{\color{blue}{l(1)}+ l(n-1)}_{\text{cut in } 1},\ l(2) + \color{red}{l(n-2)}, \cdots, \underbrace{\color{red}{l(n-2)} + l(2)}_{\text{cut in }n-2},\ l(n-1) + \color{blue}{l(1)}\ \}.$$ Therefore, $$l(n) = \max_{i=1,\cdots,\lfloor \frac{n-1}{2}\rfloor} l(i) + l(n-i).$$ Why is $$O(n^2)$$? To build up the solution $$l(n)$$, we have to compute the small instances of the problem, $$l(1), l(2),\cdots, l(n-1)$$. In each case, we have to iterate all possible cuts $$1, 2, \cdots, n - 1$$. Then, we have $$O(n)\cdot O(n)$$ running time. Your problem is a classic one (a variant of the knapsack problem). Maybe is more clear to you, if you see explicitly the overlapping into subproblems, something necessary to apply the dynamic programing paradigm, after then, is natural come up with the recursion relation. For example, when you have the rod of length $$n$$, you can cut it in so many ways, like cut in $$1$$ or $$2$$, thats it, ending with a rod of lengths $$[1$$ and $$n-1]$$ or $$[2$$ and $$n-2]$$, respectively. In each case, you find the maximum profit and the compare with the other options, as we expect. For instance, in the first case, we need the solution for the second one, because cut in $$1$$ (i.e. $$[1$$ and $$n-1]$$) means $$\text{price}(1)+l(n-1)$$, where $$l$$ is the method that solves our problem for a rod of length $$n$$. But solves $$l(n-1)$$ should consider cut in $$1$$ again, but this time in a length of $$n-2$$, that is, $$\text{price}(1) +l(n-2)$$. As we can see $$l(1)$$ was already required, and if we continue, it will be required again. Also, it repeats with $$l(n-2)$$ and others, overlapping subproblems. $$l(n):=\text{ maximun profit of cutting the rod of length n in all possible ways },$$ $$l(n)=\max \{\ \underbrace{\color{blue}{\text{price}(1)}+ l(n-1)}_{\text{cut in } 1},\ \text{price}(2) + l(n-2), \cdots, \underbrace{\text{price}(n-2) + l(2)}_{\text{cut in }n-2},\ \text{price}(n-1) + \color{blue}{l(1)}\ \}.$$ Therefore, $$l(n) = \max_{i=1,\cdots,n-1} \text{price}(i) + l(n-i).$$ Why is $$O(n^2)$$? To build up the solution $$l(n)$$, we have to compute the small instances of the problem, $$l(1), l(2),\cdots, l(n-1)$$. In each case, we have to iterate all possible cuts $$1, 2, \cdots, n - 1$$. Then, we have $$O(n)\cdot O(n)$$ running time. 1 answered Apr 8 '16 at 15:14 jonaprieto 1,34622 gold badges1212 silver badges2222 bronze badges Your problem is a classic one (a variant of the knapsack problem). Maybe is more clear to you, if you see explicitly the overlapping into subproblems, something necessary to apply the dynamic programing paradigm, after then, is natural come up with the recursion relation. For example, when you have the rod of length $$n$$, you can cut it in so many ways, like cut in $$1$$ or $$2$$, thats it, ending with a rod of lengths $$[1$$ and $$n-1]$$ or $$[2$$ and $$n-2]$$, respectively. In each case, you find the maximum profit and the compare with the other options, as we expect. For instance, in the first case, we need the solution for the second one, because cut in $$1$$ (i.e. $$[1$$ and $$n-1]$$) means $$l(1)+l(n-1)$$, where $$l$$ is the method that solves our problem for a rod of length $$n$$. But solves $$l(n-1)$$ should consider cut in $$1$$ again, but this time in a length of $$n-2$$, that is, $$l(1) +l(n-2)$$. As we can see $$l(1)$$ was already required, and if we continue, it will be required again. Also, it repeats with $$l(n-2)$$ and others, overlapping subproblems. $$l(n):=\text{ maximun profit of cutting the rod of length n in all possible ways },$$ $$l(n)=\max \{\ \underbrace{\color{blue}{l(1)}+ l(n-1)}_{\text{cut in } 1},\ l(2) + \color{red}{l(n-2)}, \cdots, \underbrace{\color{red}{l(n-2)} + l(2)}_{\text{cut in }n-2},\ l(n-1) + \color{blue}{l(1)}\ \}.$$ Therefore, $$l(n) = \max_{i=1,\cdots,\lfloor \frac{n-1}{2}\rfloor} l(i) + l(n-i).$$ Why is $$O(n^2)$$? To build up the solution $$l(n)$$, we have to compute the small instances of the problem, $$l(1), l(2),\cdots, l(n-1)$$. In each case, we have to iterate all possible cuts $$1, 2, \cdots, n - 1$$. Then, we have $$O(n)\cdot O(n)$$ running time.