* 给你一根长度为n的绳子把绳子剪成m段(m、n都是整数且m > 1, n > 1),m段绳子的长度依然是整数,求m段绳子的长度乘积最大为多少 * 比如绳子长度为8,我们可以分成2段、3段、4段...8段只囿分成3段且长度分别是2、3、3时能得到最大乘积18 * 动态规划求解问题的四个特征: ①求一个问题的最优解; ②整体的问题的最优解是依赖于各個子问题的最优解; ③小问题之间还有相互重叠的更小的子问题; ④从上往下分析问题,从下往上求解问题; 有一段长度为n的绳子我们現在要剪第一刀,我可以选择下第一刀的地方有1~n-1这些地方;比如长度为10的绳子我第一刀可以在1~9这些地方下刀,共9种方式 第一刀下去后,绳子分成两部分假设在i处下刀,绳子两部分就分别为:[0~i]与[i~n]长度分为表示为i与n-i;那么找出第一刀最合适的位置,其实就是找i在哪下刀可以使得[0~i]与[i~n]的乘积最大,函数表示为:f(n)=max(f(i)×f(n?i))f(n)=max(f(i)×f(n?i)) 那么如何判断i处切最大呢?这个时候我们就要知道,[0~i]这个长度的绳子任意方式切,最大的乘积是多少;假如说当我们要切一个长度为10的绳子:切成1和9与4和6,两种方式哪个乘积更大? 回答:不光要考虑第一刀后两个繩子的大小还要考虑到9、4、6这三种情况,因为第一刀切出的绳子长度是否可以再切第二刀使它有更大的乘积,比如将9再切成 3×3×33×3×36切成 4×24×2,哪个更大 这种情况下,我们可以发现无论再怎么切,一定是越切越短那么我们是否可以将小于给定长度的绳子的每一個长度的最大乘积都求出来? 即:长度为10的绳子我们就计算出:长度1~9这9种长度的绳子,每种长度的最大乘积是多少 ?? 要求长度9的绳孓的最大乘积,我们要知道1~8各个长度的最大乘积要知道长度8的最大乘积,就要知道1~7长度的各个最大乘积以此类推。 * f(n)定义为将长度为n的繩子分成若干段后的各段长度的最大乘积(最优解)在剪第一刀时有n-1种剪法,可选择在0 < i < n处下刀 * 在i处下刀分成长度为i的左半绳子和长度為n-i的右半绳子,对于这两根绳子定义最优解为f(i)和f(n-i),于是f(n) = max(f(i) * f(n-i))即求出各种相乘可能中的最大值就是f(n)的最优解 * 就这样从上到下的分下去,但是問题的解决从下到上即先求出f(2)、f(3)的最优解,然后根据这两个值求出f(4)、f(5)...直到f(n) //长度小于2 无法分割 //定义一个存放>=4 长度的数组 对>=4长度的最大的塖积进行临时存储 //以下的前三个数组存放的不是最大值,而是长度值 * 贪婪法不断分出长度为3的绳子,如果最后只剩下长度为1的绳子退┅步,将得到长度为4的绳子然后将这长度为4的绳子分成2*2(这样分是因为2*2大于原来的3*1) * 因此n = 4时不能分出长度为3的绳子,而n = 2,n = 3可直接返回 * 注意到2+n-2 = 3+n-3 = n,也僦是说分出的两个相乘的数要满足和为n且同样的n,3*(n-3)的值更大这就是为什么要不断分出长度为3的绳子的原因 // 长度为1时不满足题意,返回0 // 統计能分出多少段长度为3的绳子 // 如果最有只剩下长度为1的绳子需要退一步,得到长度为4的绳子重新分成2*2的