offer 第14-I题 剪绳子(medium)

该系列文章为本人刷leetcode的记录,主要旨在分享刷题的思路及算法解析(尽可能的一题多解),另方便自己日后查阅回顾。代码的实现语言是python和go。

想进大厂免不了刷题,一起加油吧，小伙伴们！

链接: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

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

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

• 2 <= n <= 58

分析:该题具有明显的动态规划公式(迭代解法);递归解法(会超时);

解法1:尾递归或者记忆递归

解法2: 动态规划

假设n为绳长;dp[n]表示n长度的绳子剪成m段后的最大长度;

其中如果长度为n的绳子剪完i后不再继续剪了,则有dp[n]=i*(n-i);

如果剪完后还继续剪(n-i)这一段绳的话,则有dp[n]=i*dp[n-i];

所以dp[n]=max(dp[n],i*(n-i), i *dp[n-i]);因为dp[n]一开始就可能不剪的时候已经最大了;

def cuttingRope(n:int) -> int:

    #方法1:尾递归;这题有点像阶乘的思想
    #递归就是不断尝试;剪完第一刀后开始剪第2刀,依次类推;第一刀有n-1种剪法;
    #这题也像走迷宫那题;不过走迷宫那题走完第一个点后只能往上下左右四个点走;这题剪完第一刀i后,实际上下一步尝试的范围是(0,n-i)

    #
    max_val = 1
    # #传递的参数是剪完当前段还剩多少长度的绳子;以及剪完当前长度绳子后的乘积;
    def dfs(n0,mul):
        #尾递归终止条件
        nonlocal max_val

        #剪到最后一段绳子如果剩3及以下都不应该再剪了;此时已经是最大了
        if n0==0: max_val=max(max_val,mul)
        elif n0<=3: max_val = max(max_val,mul*n0)
        else:
            #除去中间和最后一段按理说正经的递归写法应该是如下;但是这样写会递归会超时;因为有大量相同的子问题被重复计算了;
            # for i in range(1,int(n/2)+1):
            #     dfs(n0-i,mul*i)
            # 解决方法1:记忆化递归;算出来子问题的解进行存储;遇到重复的就直接读取就行
            #解决方法2:尾递归;实际上在进行中间段的切割的时候,每次要么切割2或者切割3;其余切割其他数字的问题都可以转化为切割2或者3;
            #所以只用尝试切割2和3就行;
            #return dfs(n0-2,mul*2) or dfs(n0-3,mul*3)
            #实际上每一段切成3是结果是最大的;因为中间段的绳子一定是2或者3的倍数;假如恰好是2和3的公倍数;易证这时候都切成3肯定更大;
            #假如不是公倍数;比如中间段是2n;那么一定可以转换成m=3*n1+2;同理m=2*n2+3;故又可以变成公倍数问题;肯定取3更大;
            return dfs(n0-3,mul*3)



    # #剪第一刀;如果n=2时第一刀不能直接剪2;当n>3时候肯定是从2开始剪起更大;
    for i in range(1,int(n/2)+1):
        dfs(n-i,i)



    return max_val



    #方法2:动态规划;
    #该题的动态规划公式
    #dp[n] = dp[n-i]*i
    #如果n-i也不再继续剪了那么:dp[n]=i*(n-i)
    # 其中dp[0]=1;dp[1]=1;dp[2]=1;dp[3]=2

  #  动态规划的过程就是从最开始的一直迭代到最后的过程;
  #   dp=[1]*(n+1)
  #   dp[0]=1
  #   dp[1]=1
  #   dp[2]=2
  #   for i in range(3,n+1):
  #       for j  in range(1,i):
  #           #对绳长i来说如果剪一刀j,之后如果不剪了那么绳长就是(j)*(i-j),但是如果(i-j)这一段还要继续剪那么长度就是j*dp[i-j]
  #           dp[i] = max(dp[i-j]*j,j*(i-j),dp[i])
  #
  #
  #   return dp[n]

func max_int(n1,n2 int) int{
	if n1>=n2{return n1
	}else {return n2}
}

func max_int3(n1,n2,n3 int) int{
	//使用冒泡排序
	if n1>=n2{n1,n2=n2,n1}
	if n2>n3{n2,n3=n3,n2}
	return n3

}

func cuttingRope(n int) int{
	方法1:尾递归
	//max_val := 1
	//var recur func(n0,mul int) int
	//recur = func(n0,mul int) int{
	//	//递归终止条件
	//	if n0==0{ max_val= max_int(max_val,mul)
	//	}else if n0<=3{ max_val=max_int(max_val,mul*n0)
	//	}else{
	//		return recur(n0-3,mul*3)
	//
	//	}
	//	return -1
	//
	//
	//}
	//i:=0;
	//for ;i 
总结 
注意下递归会超时的问题;需要使用尾递归或者记忆化递归;
 
动态规划解法时候要考虑全面,不要漏掉其他可能最大值可能出现的情况;