【剑指offer】剪绳子（Python）

1. 聪明解法

绳子拆成 1 和 n-1， 1*(n-1) - n = -1 < 0，乘积变小，所以不能出现长度为 1 的绳子

绳子拆成 2 和 n-2， 2*(n-2) - n = n-4 >= 0(n>=4)，当n>=4时乘积变大

绳子拆成 3 和 n-3， 3*(n-3) - n = 2n-9 >= 0(n>=5)，当n>=5时乘积变大

绳子拆成 4 和 n-4，因为 4 = 2*2 所以效果和2一样

绳子拆成 5 和 n-5，因为 5=2+3，而5<2*3，所以不能出现长度为5的绳子，拆成2 和3

绳子拆成 6 和 n-6，因为 6=3+3，而6<3*3，所以不能出现长度为6的绳子，拆成3 和3。6=2+2+2，但是3(n-3)-2(n-2)=n-5>=0(n>=5)，所以n>=5时，拆成3比拆成2更好

。。。

只考虑将绳子拆成2和3，并且优先3，当拆到绳子长度n=4时，出现3+1<2*2，拆成2.

# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        # 只考虑拆成2和3，且优先3
        if number < 2:
            return 0
        if number == 2:
            return 1
        if number == 3:
            return 2
        timesOf3 = number // 3
        if number - timesOf3 * 3 == 1:
            timesOf3 -= 1
        timesOf2 = (number - timesOf3 * 3) // 2
        return int(pow(3, timesOf3)) * int(pow(2, timesOf2))

2. 暴力解法
暴力解法，空间超了，但是可以看一下思路。“自上而下”求解

递归函数的设计和功能：back_track(n); 含义是：求长度为n的数，最后分段后的最大乘积，这里我们不需要关心分成多少段
递归函数的终止条件: 如果n <= 4, 显然back_track(n) = n，初始条件也就是我们不用计算就能得到的。
下一步递归：对于长度n，我们需要减少递归参数n，如果第一段为1，显然下一步递归为back_track(n-1),如果第一段为2，则下一步递归为
back_track(n-2)...因为要至少分2段，所以，最后一次可能的情况为最后一段为n-1, 下一步递归为back_track(1)，因此，每一步可能的结果为
1 * back_track(n-1), 2 * back_track(n-2), ..., (n-1) * back_track(1),在n-1种情况中取一个最大值即可。这里我们不用关系back_track(n-1)等的值为多少，因为最终会递归到我们的终止条件，因此绝对是可以求出来。

# -*- coding:utf-8 -*-
class Solution:
    ret = 0
    def cutRope(self, number):
        # write code here
        # 暴力递归 1. 递归函数功能 2. 递归终止条件 3. 下一步递归
        self.ret = 0
        if number == 2:
            return 1
        elif number == 3:
            return 2
        return self.back_track(number)
    def back_track(self,n):
        # 求长度为n的数分段后的最大乘积
        if n <= 4 :
            return n
        for i in range(n):
            self.ret = max(self.ret, i * self.back_track(n-i))
        return self.ret

3. 带备忘录的暴力求解

使用一个备忘录，减少求解冗余，直接在暴力求解代码上修改：

注意python 数组的初始化方法，mark = [-1 for i in range(number+1)]

求解效率不高，打败20%的代码

# -*- coding:utf-8 -*-
class Solution:
    ret = 0
    def cutRope(self, number):
        # write code here
        # 暴力递归 1. 递归函数功能 2. 递归终止条件 3. 下一步递归
        self.ret = 0
        mark = [-1 for i in range(number+1)]
        if number == 2:
            return 1
        elif number == 3:
            return 2
        return self.back_track(number,mark)
    def back_track(self,n,mark):
        # 求长度为n的数分段后的最大乘积
        if n <= 4 :
            return n
        if mark[n] != -1:
            return mark[n]
        for i in range(1,n):
            self.ret = max(self.ret, i * self.back_track(n-i,mark))
        mark[n] = self.ret
        return mark[n]

4. 动态规划

一般，动态规划有以下几种分类：

最值型动态规划，比如求最大，最小值是多少
计数型动态规划，比如换硬币，有多少种换法
坐标型动态规划，比如在m*n矩阵求最值型，计数型，一般是二维矩阵
区间型动态规划，比如在区间中求最值

动态规划是“自下而上”求解。

# -*- coding:utf-8 -*-
class Solution:
    ret = 0
    def cutRope(self, number):
        # write code here
        # 动态规划
        if number == 2:
            return 1
        elif number == 3:
            return 2
        mark = [-1 for i in range(number+1)]
        for i in range(1,5):
            mark[i] = i
        for i in range(5, number+1):
            for j in range(1, i):
                mark[i] = max(mark[i], j*mark[i-j])
        return mark[number]

题解 | #剪绳子#

【剑指offer】剪绳子（Python）