在本教程中，我们将学习杆切割问题。
问题陈述：
您获得了长度为n的鱼竿，并且需要以某种方式切割鳕鱼，以便将其出售以获取最大利润。您还会得到一张价格表，其中给出了一根杆的价值。
例
因此，根据上表，如果您切割长度为1的杆，则可以看到2 rs。
同样，如果您将棒切成2号长度，则可以7 rs的价格出售
同样，如果您将棒切成3长度，则可以10 rs的价格出售
根据问题，您需要找到如何切割杆的方法，以便获得最大的利润。
在我们的示例中，杆的长度为5。
如果您不剪掉整个杆，则利润为12 rs。
但是，如果您在长度3和长度2处切割杆，则总利润将为7 + 10 =17。这使我们获得了最大利润。
那么，如何解决这个问题呢？
一种方法是使用蛮力方法。在蛮力法中，对于长度n = 4，我们得到以下组合。
1 1 1 1
1 1 2
1 2 1
2 1 1
3 1
2 2
1 3
4
从上面我们总共有8种不同的方法来切割长度为4的杆。然后，我们需要找到所有组合的利润并找到其中的最大值。然后我们得出结果。
但这将需要2 ^ n-1，即2 ^ 4-1 = 2 ^ 3 = 8种不同的方式。
因此，最坏情况下的时间复杂度将为O（2 ^ n-1）。
如果使用DP，我们可以将时间复杂度降低到O（n ^ 2）。
让我们看看如何将DP应用于我们的问题。
通常，对于DP，我们需要一个DP矩阵。初始矩阵如下：
在该行上，我们将具有杆的长度。在该列上，我们将具有可出售的长度件数。
在表中，我们将填写利润。最后，我们将获得最大的利润。
当标尺长度为0时，利润也将为0。
因此，我们可以首先填充矩阵，如下所示：
从“ 0”开始每个DP矩阵很重要，这样您在解决子问题时会很清楚。
转到下一行。 “第1行”。我们有长度为1的杆件，因此对于每个不同的长度，我们需要使用杆件1的组合并计算利润。
对于长度1，利润将为2。
对于长度2，利润将为4。
对于长度3，利润将为6。
对于长度4，利润将是8。
对于长度5，利润将是10。
因此，更新后的矩阵将如下所示：
现在，对于下一行，我们具有[1、2]的杆件组合。现在我们将如下填充数组。
长度为1时，您只能使用1个长度。因此利润为2。
在长度2处，您可以有2个选择。您可以使用长度为1的杆两次或长度为2的杆一次。当我们确定最大利润时，我们将计算两种情况下的利润。
即
1件+ 1件= 2 + 2 = 4
杆的长度2 = 7。
由于需要最大值，因此我们选择7。
同样，对于长度3，我们可以将杆切成1长度&2个长度。因此利润是2 + 7 = 9
同样，对于长度4，我们可以将杆切割2个长度&2个长度。因此利润是7 + 7 = 14
同样，对于长度5，我们可以将棒切成2长度& 2 lengths &1个长度。因此利润是7 + 7 + 2 = 16
因此，我们更新的DP表如下：
同样，我们将在下一行中查找。在下一行中，我们可以选择长度为[1、2、3]的杆。
对于长度1，利润为2。
对于长度2，利润为7。我们从上方获取这两个值。
对于长度3，我们可以将棒切成2长度&1个长度。因此，利润为9，或者我们可以卖出长度为3的整个杆以获取利润10。我们选择最大利润，即10。
对于长度4，我们可以将杆切割2个长度&2个长度。因此利润是14或我们可以切割长度3的杆&1个利润长度12。我们选择最大利润，即14。
对于长度5，我们可以将杆切成3长度&2个长度。因此利润为17。
更新后的DP表如下：
通过查看上表，我们可以得出DP公式？是的，我们可以这样做，如下所示：
对于i = 1到n
对于j = 1到n
如果我< j
dp [i] [j] = dp [i-1] [j]
其他
dp [i] [j] = max（dp [i-1] [j]，arr [i] + dp [i] [j-1]）
同样，我们将求解矩阵。
最终矩阵如下：
因此，结果。
C ++解决方案
#include<iostream>
using namespace std;
int get_max(int a, int b) { return (a > b)? a : b;}
int rod_cutting_dp_solution(int price[], int n)
{
int dp_table[n+1];
dp_table[0] = 0;
int i, j;
for (i = 1; i<=n; i++)
{
int max_val = INT_MIN;
for (j = 0; j < i; j++)
max_val = get_max(max_val, price[j] + dp_table[i-j-1]);
dp_table[i] = max_val;
}
return dp_table[n];
}
int main()
{
int arr[] = {2, 7, 10, 11, 12};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Maximum Value is "<< rod_cutting_dp_solution(arr, size)<<endl;
return 0;
}
// Maximum Value is 17
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
