剑指offer：剪绳子-创新互联

题目：
给定一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0] k[1] … *k[m]可能的大乘积是多少？

10年的金凤网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。营销型网站的优势是能够根据用户设备显示端的尺寸不同，自动调整金凤建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。创新互联从事“金凤网站设计”,“金凤网站推广”以来，每个客户项目都认真落实执行。

例子：
例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的大乘积是18。

def cutRopeDP(length):
    """
    在剪绳子这个题目中，由于必须要剪一刀，因此会导致当所给的绳子长度是小于4的时候，剪完之后的长度
    小于剪之前的长度。但是我们在递推的时候，例如求f(5) = max{f(1)*f(4), f(2)*f(3)} = 6
    如果令f(3)=2的话，将导致递推公式错误，因此，对于小于4的输入，我们特殊处理。
    """
    if length < 2:  # 由于至少剪一刀，所以当长度小于2的时候无法剪，因此返回0
        return 0
    if length in (2, 3):
        return {2: 1, 3: 2}[length]

    products = [0, 1, 2, 3]  # 初始化长度小于4的输入所对应的输出的大值
    for i in range(4, length + 1):
        max_product = 0
        # 对于每一个输入，我们需要遍历它所有可能的输出然后挑出最优的
        for j in range(1, i // 2 + 1):
            max_product = max(max_product, products[j] * products[i - j])
        products.append(max_product)

    return products[-1]

def cutRopeGreedy(length):
    """
    当n>=5的时候，2(n-2) > n and 3(n-3) > n; 3(n-3) >= 2(n-2)
    也就是说当长度大于5的时候，剪出长度为3的段数越多最后的乘积越大

    但是对于长度为4的时候，如果剪出一段长度为3，另一段长度为1，则乘积为3，小于剪出两段长度为2
    因此，当最后剩下4的时候，不是剪成1,3而是剪成2,2

    但是使用贪心方法求解最优解的时候需要非常tricky，因此优先尝试dp吧
    """
    if length < 2:  # 由于至少剪一刀，所以当长度小于2的时候无法剪，因此返回0
        return 0
    if length in (2, 3):
        return {2: 1, 3: 2}[length]
    timesOf3 = length // 3
    if length - timesOf3 * 3 == 1:
        timesOf3 -= 1
    timesOf2 = (length - timesOf3 * 3) // 2
    return 3 ** timesOf3 * 2 ** timesOf2

另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

标题名称：剑指offer：剪绳子-创新互联
网站URL：http://6mz.cn/article/dsijji.html