劍指offer：剪繩子

題目：
給定一根長(zhǎng)度為n的繩子，請(qǐng)把繩子剪成m段（m、n都是整數(shù)，n>1并且m>1），每段繩子的長(zhǎng)度記為k[0],k[1],…,k[m]。請(qǐng)問(wèn)k[0] k[1] … *k[m]可能的最大乘積是多少？

創(chuàng)新互聯(lián)建站主營(yíng)武都網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,app軟件定制開(kāi)發(fā),武都h5微信平臺(tái)小程序開(kāi)發(fā)搭建,武都網(wǎng)站營(yíng)銷推廣歡迎武都等地區(qū)企業(yè)咨詢

例子：
例如，當(dāng)繩子的長(zhǎng)度是8時(shí)，我們把它剪成長(zhǎng)度分別為2、3、3的三段，此時(shí)得到的最大乘積是18。

def cutRopeDP(length):
    """
    在剪繩子這個(gè)題目中，由于必須要剪一刀，因此會(huì)導(dǎo)致當(dāng)所給的繩子長(zhǎng)度是小于4的時(shí)候，剪完之后的長(zhǎng)度
    小于剪之前的長(zhǎng)度。但是我們?cè)谶f推的時(shí)候，例如求f(5) = max{f(1)*f(4), f(2)*f(3)} = 6
    如果令f(3)=2的話，將導(dǎo)致遞推公式錯(cuò)誤，因此，對(duì)于小于4的輸入，我們特殊處理。
    """
    if length < 2:  # 由于至少剪一刀，所以當(dāng)長(zhǎng)度小于2的時(shí)候無(wú)法剪，因此返回0
        return 0
    if length in (2, 3):
        return {2: 1, 3: 2}[length]

    products = [0, 1, 2, 3]  # 初始化長(zhǎng)度小于4的輸入所對(duì)應(yīng)的輸出的最大值
    for i in range(4, length + 1):
        max_product = 0
        # 對(duì)于每一個(gè)輸入，我們需要遍歷它所有可能的輸出然后挑出最優(yōu)的
        for j in range(1, i // 2 + 1):
            max_product = max(max_product, products[j] * products[i - j])
        products.append(max_product)

    return products[-1]

def cutRopeGreedy(length):
    """
    當(dāng)n>=5的時(shí)候，2(n-2) > n and 3(n-3) > n; 3(n-3) >= 2(n-2)
    也就是說(shuō)當(dāng)長(zhǎng)度大于5的時(shí)候，剪出長(zhǎng)度為3的段數(shù)越多最后的乘積越大

    但是對(duì)于長(zhǎng)度為4的時(shí)候，如果剪出一段長(zhǎng)度為3，另一段長(zhǎng)度為1，則乘積為3，小于剪出兩段長(zhǎng)度為2
    因此，當(dāng)最后剩下4的時(shí)候，不是剪成1,3而是剪成2,2

    但是使用貪心方法求解最優(yōu)解的時(shí)候需要非常tricky，因此優(yōu)先嘗試dp吧
    """
    if length < 2:  # 由于至少剪一刀，所以當(dāng)長(zhǎng)度小于2的時(shí)候無(wú)法剪，因此返回0
        return 0
    if length in (2, 3):
        return {2: 1, 3: 2}[length]
    timesOf3 = length // 3
    if length - timesOf3 * 3 == 1:
        timesOf3 -= 1
    timesOf2 = (length - timesOf3 * 3) // 2
    return 3 ** timesOf3 * 2 ** timesOf2

網(wǎng)站題目：劍指offer：剪繩子
當(dāng)前URL：http://muchs.cn/article16/gdipdg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、自適應(yīng)網(wǎng)站、品牌網(wǎng)站設(shè)計(jì)、面包屑導(dǎo)航、電子商務(wù)、虛擬主機(jī)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)