題目描述

給你一根長(zhǎng)度為 n 的繩子，請(qǐng)把繩子剪成整數(shù)長(zhǎng)度的 m 段（m、n都是整數(shù)，n>1并且m>1），每段繩子的長(zhǎng)度記為 k[0],k[1]...k[m-1] 。請(qǐng)問(wèn) k[0]k[1]...*k[m-1] 可能的最大乘積是多少？例如，當(dāng)繩子的長(zhǎng)度是8時(shí)，我們把它剪成長(zhǎng)度分別為2、3、3的三段，此時(shí)得到的最大乘積是18。

示例 1：

輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1
示例 2:

輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：

2 <= n <= 58

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof

解題思路

參考題解https://leetcode-cn.com/problems/integer-break/solution/343-zheng-shu-chai-fen-tan-xin-by-jyd/。
可以證明當(dāng)繩子以3為一段剪開(kāi)時(shí)，能得到每一段繩子長(zhǎng)度乘積的最優(yōu)解。但是當(dāng)以3剪開(kāi)有剩余時(shí)，需要分剩余為0、1、2三種情況進(jìn)行討論：

1. 當(dāng)n = 0時(shí)，得到3**a；
2. 當(dāng)n = 1時(shí)，由于1 + 3分為2 * 2會(huì)比1 * 3乘積大，所以得到3^(a-1) * 4；
3. 當(dāng)n = 2時(shí)，得到3^a * 2；

代碼

int cuttingRope(int n){
    int a, b;

    if(n <= 3)
        return (n - 1);
    a = n / 3;
    b = n % 3;
    if(b == 0)
        return (pow(3, a));
    else if(b == 1)
        return (4 * pow(3, a - 1));
    else
        return (2 * pow(3, a));
}

測(cè)試代碼及結(jié)果

#include<stdio.h>
#include<math.h>

int cuttingRope(int n);

int main(void)
{
    
    // 功能測(cè)試
    printf("%d\n", cuttingRope(5));

    // 邊界值測(cè)試
    printf("%d\n", cuttingRope(0));
    printf("%d\n", cuttingRope(1));
    printf("%d\n", cuttingRope(2));
    printf("%d\n", cuttingRope(3));

    return 0;
}

執(zhí)行結(jié)果