剪绳子

题目描述

给定一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]* k[1] * … *k[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

思路

这是一道动态规划问题。整体问题的最优解依赖于各个子问题的最优解。首先是对于问题的拆解，第一刀的时候，有n-1种选择，如何选出最优的一刀？ 在n-1个位置尝试，找到相乘最大的那一刀所在的位置。 f(n) = max{f(i)*f(n-i)}。
这里最初一直没想明白为什么这样一刀一刀选下去就是最优解。后来思考过程如下，假设第一刀不是最优解，那一定还有其他切法会使得乘积更大，所以无论怎么切，一定会切出来两段绳子，导致乘积最大。那切出的每一段绳子，一定可以分解成另外两小段的乘积。
这里的思考过程是从上至下，但是在实际的操作中，可以先分析最小的子问题，然后记录子问题的解，从下至上解决问题。
在代码实现中构建了一个ans数组，这里的ans记录了切绳子时对应长度可表示的最大值。ans[1]就表示长度为1的长度最大值（假设绳子长度大于2）。ans[2]表示切分时，切到一段为2时的最大值。这里要注意，如果绳子的长度是2，那最大是切成1和1两段。但是如果绳子大于2，其中一段切成长度为2，那这里ans[2]最大值就是2。ans[3]表示切了一段绳子的长度为3，那他最大可以用3来表示，也就是直接用一段长度为3的绳子表示。
1，2，3这三个长度就是基本的情况，如果长度再长就可以分解为这3个长度来组合解决了。
具体的代码实现如下。

代码

def maxCutting(length):
    if length<2:
        return 0
    if length ==2:
        return 1
    if length ==3:
        return 2
    ans =[0]*(length+1)
    ans[0] = 0
    ans[1] = 1
    ans[2] = 2
    ans[3] = 3
    for i in range(4,length+1):
        result = 0
        end = int(i/2)+1
        for j in range(1,end):
            temp = ans[j] * ans[i-j]
            if temp > result:
                result = temp
            ans[i] = result
    return ans[-1]
print(maxCutting(8))