题目地址：

https://www.lintcode.com/problem/cutting-a-rod/description

有一根长为$n$的杆子，再给出长为$1\sim n$的杆子的价值$c[i]$，允许将这根杆子切成若干长度为整数的短杆子，问能得到的最大价值是多少。

思路是动态规划。设$f[i]$为长度为$i$的杆子能切出的最大价值。我们可以按照最后一刀切在什么位置来分类，切的位置可以描述为$0+i,1+(i-1),2+(i-2),...,(i-1)+1,i+0$这样，需要注意，不切也是一种方案。所以有：$$\begin{gathered} f[i]=\max \{c[i],f[i-1]+f[1],f[i-2]+f[2],...,f[1]+f[i-1]\} \\ =\underset{1\le j\le i/2}{\max }\{c[i],f[i-j]+f[j]\} \end{gathered}$$代码如下：

public class Solution { /** * @param prices: the prices * @param n: the length of rod * @return: the max value */ public int cutting(int[] prices, int n) { // Write your code here int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { dp[i] = prices[i - 1]; for (int j = 1; j <= i / 2; j++) { dp[i] = Math.max(dp[i], dp[i - j] + dp[j]); } } return dp[n]; } }

时间复杂度$O(n^2)$，空间$O(n)$。