剑指offer-动态规划-贪心算法--剪绳子-python

题目描述

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

输入描述:

输入一个数n，意义见题面。（2 <= n <= 60）

思路：动态规划：

有这几个特殊情况：当n为0时，没发裁输出为0n为1时，最大分子为1，输出1
n为2时，最大分子为2，输出2
n为3时，最大分子为2，输出2
然后从4开始遍历，将切割的所有可能找出来，，由于当i大于n//2时，就不用在计算了，重复计算，然后与之相乘

temp = prod[i] * prod[n - i]
最后将结果与max作比较，放入数组中去。

class Solution:

    def cutRope(self, number):

        # write code here

        # res=1

        if number <= 1:

            return 0

        elif number <= 2:

            return 1

        elif number <= 3:

            return 2

        prod = [0, 1, 2, 3]

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

            maxs = 0

            for i in range(1, n//2):

                temp = prod[i] * prod[n - i]

                if temp > maxs:

                    maxs = temp

            prod.append(maxs)

        return prod[-1]

算法时间复杂度O(n²)，空间复杂度O(n)。

思路：贪心算法：

等号在n=5时成立。
所以应把绳子剪成尽量多的3，让剩下的都是2这样的组合。

class Solution:

    def cutRope(self, number):

        # write code here

        # res=1

        if number <= 1:

            return 0

        elif number <= 2:

            return 1

        elif number <= 3:

            return 2

        elif number <= 4:

            return 4

        timeofthree = number//3

        if number -timeofthree*3 ==1:

            timeofthree-=1

        timeoftwo = (number-timeofthree*3)//2

        return pow(3,timeoftwo)*pow(2,timeoftwo)

剑指offer-动态规划-贪心算法--剪绳子-python的相关教程结束。