【每日一题20220524】剪绳子

: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
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
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
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
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))
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]
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
    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

关闭