杆切割
进阶杆切割是 0-1 背包的变体，每种长度的切割可以使用多次。
// 算法讲解
杆切割
求如何切割杆使总收益最大。
待机
速度 中
待机 ⌨1int rodCutting(vector<int>& prices, int n) {
2 vector<int> dp(n + 1, 0);
3 for (int i = 1; i <= n; i++) {
4 for (int j = 1; j <= i; j++) {
5 dp[i] = max(dp[i], prices[j] + dp[i - j]);
6 }
7 }
8 return dp[n];
9}
复杂度分析
时间 O(n²)
空间 O(n)
最优 O(n²)
最坏 O(n²)
算法讲解
给定一根长度为 n 的杆和每种长度的价格，求如何切割使总收益最大。
dp[i] 表示长度为 i 的杆的最大收益。
转移：dp[i] = max(price[j] + dp[i-j])，枚举第一刀切在位置 j。
时间复杂度 O(n²)，空间复杂度 O(n)。