一、题目：
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 58
二、分析：
1.问题分析： 遇到这种把一个整数一次一次分成若干整数，然后这些整数相乘或相加的最大值的问题时，可以先考虑动态规划。 一个长度为n的绳子，第一次把它剪一段长度为j，剩下的长度为n-j，第二次又继续对n-j进行重复的操作，或者可以不剪.（这样的问题可以依次分解成若干个小问题，并且重复相同的步骤，可以考虑用动态规划）
2.确定dp数组及其下标含义： dp[i]：表示长度为i的绳子剪成若干段，这些段的最大乘积。
3.初始化： 0和1不可以剪，所以dp[1]=dp[0]=0。
4.推导公式： dp[i] = max(j*(i-j),dp[i-j])，j*(i-j)表示长度为i的绳子，剪了j，剩下的就不剪了；dp[i-j]表示剪了j，剩下的继续剪。dp[i]要多次遍历才能找到，所以还要和前一次遍历得到的dp[i]比较看看谁大。
4.遍历： 从长度为2开始遍历到n，找每一个长度下的最大乘积，因为最后要返回dp[n]；dp[i]是要多次遍历寻找的，比如长度为4，第一次剪了1，剩下的不知道要剪1还是2还是3，才能保证最后的乘积最大。（具体看代码再回头分析）
class Solution {
public:
int cuttingRope(int n) {
vector<int> dp(n+1);
dp[0]=dp[1]=0;
for(int i=2;i<=n;i++){//找最大乘积要保证前一次也是最大乘积
for(int j=1;j<i;j++){
dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]));//要和前一次遍历的dp[i]比较大小
}
}
return dp[n];
}
};
三、复杂度分析
1.时间复杂度：O(n^2)
其中 n 是给定的正整数。对于从 2到 n 的每一个整数都要计算对应的 dp 值，计算一个整数对应的dp 值需要 O(n) 的时间复杂度，因此总时间复杂度是 O(n^2)。
2.空间复杂度：O(n)，其中 n 是给定的正整数。创建一个数组 dp，其长度为 n+1。
标签：遍历,14,Offer,复杂度,绳子,整数,长度,dp From： https://www.cnblogs.com/lxpblogs/p/16654716.html