给你根长度为n的绳子,请把绳子剪成n段(m,n都是整数并且m,n>1)每段绳子长度记为k[0],k[1]...k[m],请问k[0]k[1]...*k[m]的最大乘积是多少 例如,当n=8时,剪成2,3,3的三段,得到最大乘积18
动态规划: 如果是求最优解,通常是最大值最小值,而且该问题能够分解成若干个子问题,并且子问题间还有重叠的更小的子问题.就可以考虑动态规划来解决. 如本例,假设乘积最大值为f(n), 假设我们第一刀剪在长度为i(0<i<n)的位置, 于是把绳子剪成了i和n-i两段, 我们要得到问题的最优解f(n), 那么要用最优的方法把i和n-i的两段分别剪成若干段,使它们各自剪出的绳子乘积最大.也就是说整体问题的最优解是依赖与各个子问题的最优解.