【每日一题20220524】剪绳子

兴趣爱好交流 每日一题
#1

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

【示例】
输入：8
输出：18
解释：因为8 = 2 +3 +3 , 所以233=18

题目难度：简单
题目来源：牛客网-剪绳子

def solution(n: int)-> int:
    # your code here

assert solution(8) == 18
assert solution(2) == 1
#2 
def solution(n: int) -> int:
    # 初始化动态规划列表
    dp = [0] * (n+1)
    if 2 <= n <= 60:
        # 绳子长度 >= 2.
        for i in range(2, n+1):
            # 每次剪的长度为j的绳子，绳子的变化范围为：1, number(绳子长度)-1.
            for j in range(1, i):
                # dp[i]：上一次剪后的最大乘积值.
                # 剩余部分有两种情况：继续剪-> dp[i-j]， 不继续剪-> i-j.
                dp[i] = max(dp[i], j*max(dp[i-j], i-j))
        return dp[n]
    else:
        -1


assert solution(8) == 18
assert solution(2) == 1
#3 
def solution(n: int)-> int:
    if n <=3:
        return n-1
    elif n >3:
        if n%3==0:
            return 3**(n//3)
        elif n%3==1:
            return ((3**((n//3)-1))*4)
        elif n%3==2:
            return ((3**(n//3))*2)
1 Like
#4 
def solution(n: int):
    if n <= 3:
        return n-1
    # 如果绳子被3整除，就有 n //3 段
    elif n % 3 ==0:
        return 3**(n//3)
    #如果绳子除以3，余1，就有 3**（n //3 -1 ）*2*2
    elif n % 3 ==1:
        return 3**(n//3-1) * 2 *2
    # 如果绳子除以3，余2，就有 3**（n //3  ）*2
    else:
        return 3**(n//3)*2
#5 
import math
def cut(m,max):
    #cut_max指每次新绳子所剪掉的最长部分，cut_rest是剩余部分
    cut_max=int(math.sqrt(m))+1
    cut_rest=m-cut_max
    sum=cut_rest*cut_max
    if(sum<=m): #sum<=m递归结束条件
        return m
    else:
        return cut_max*cut(cut_rest,max) #x没变，表示普通绳子的最长部分，作用就是与长度为本身绳长为2，3的区分

def solution(n: int)-> int:
    if n <=3:
        return n-1
    elif n >3:
        max = int(math.sqrt(n) + 1)
        return cut(n,max)

print(solution(8))
#6 
def cutRope(n: int) -> int:
    if n == 1:
        return 0
    if n == 2:
        return 1
    if n == 3:
        return 2
    #1为最小单位数，不用拆，2,3越拆越小，所以也不用拆，本身就是最大乘因数
    pro = [0,1,2,3]
    for i in range(4,n+1):
        max = 0
        for j in range(1,i//2+1):
            tmp = pro[j]*pro[i-j]
            if tmp > max:
                max = tmp
        pro.append(max)
    return pro[n]
#7 
def solution(n: int)-> int:
    # your code here
    sum = []
    for i in range(1, n):
        if n % i != 0:
            s = i ** (n // i) * (n % i)
        else:
            s = i ** (n // i)
        sum.append(s)
    return max(sum)


assert solution(8) == 18
assert solution(2) == 1
assert solution(11) == 54
#8 
    def cutRope(n: int) -> int:
        max_parts=n//2
        result=0
        for i in range(1,max_parts):
            avg=n//i
            md=n%i
            v=max((avg**(i-md))*((avg+1)**md),avg**i)
            if v>result:
                result=v
        return result
关闭