剑指offer 面试14题

面试14题：

题目：剪绳子

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

解题思路：基于动态规划和贪婪算法，详见剑指offer P96

解题代码：

# -*- coding:utf-8 -*-

class Solution:

    def MaxProductAfterCut(self, n):

        # 动态规划

        if n<2:

            return 0

        if n==2:

            return 1

        if n==3:

            return 2

        products=[0]*(n+1)

        products[0]=0

        products[1]=1

        products[2]=2

        products[3]=3

        for i in range(4,n+1):

            max=0

            for j in range(1,i//2+1):

                product=products[j]*products[i-j]

                if product>max:

                    max=product

            products[i]=max

        #print(products)

        return products[n]

    def MaxProductAfterCut2(self, n):

        # 贪婪算法

        if n < 2:

            return 0

        if n==2:

            return 1

        if n==3:

            return 2

        timesOf3 = n//3

        if n - timesOf3*3 == 1:

            timesOf3 -= 1

        timesOf2 = (n - timesOf3 * 3)//2

        return (3**timesOf3) * (2**timesOf2)

if __name__=="__main__":

    print(Solution().MaxProductAfterCut(8))

    print(Solution().MaxProductAfterCut(10))

    #print(Solution().NumberOf1(0))

    print(Solution().MaxProductAfterCut2(8))

    print(Solution().MaxProductAfterCut2(10))