给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，2≤n≤58 并且 m≥2）。 每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少？ 例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。 样例 输入：8 输出：18
思路： 动态规划问题，可以设想绳子每次剪为两端，并且如果总的乘积最大，即每段的乘积都得最大。 C++代码：
class Solution { public: int maxProductAfterCutting(int length) { if(length < 2){ return 0; }else if(length == 2){ return 1; }else if(length == 3){ return 2; } vector<int> max_len(length + 1, 0); max_len[0] = 0; max_len[1] = 1; max_len[2] = 2; max_len[3] = 3; for(int i = 4; i <= length; i++){ int max = 0; for(int j = 1; j <= i / 2; j++){ if(max < max_len[j] * max_len[i - j]){ max = max_len[j] * max_len[i - j]; } } max_len[i] = max; } return max_len[length]; } };python 代码：
class Solution(object): def maxProductAfterCutting(self,length): """ :type length: int :rtype: int """ if length < 2: return 0 elif length == 2: return 1 elif length == 3: return 2 num_len = [] num_len.append(0); num_len.append(1); num_len.append(2); num_len.append(3); for i in range(4, length + 1): max = 0 for j in range(1, i // 2 + 1): if max < num_len[j] * num_len[i - j]: max = num_len[j] * num_len[i - j] num_len.append(max) return num_len[length]