題目描述
給你一根長(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)問 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
來源：力扣（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為一段剪開時(shí)腔呜，能得到每一段繩子長(zhǎng)度乘積的最優(yōu)解。但是當(dāng)以3剪開有剩余時(shí)再悼，需要分剩余為0核畴、1冲九、2三種情況進(jìn)行討論：
- 當(dāng)n = 0時(shí)谤草，得到3**a；
- 當(dāng)n = 1時(shí)娘侍，由于1 + 3分為2 * 2會(huì)比1 * 3乘積大咖刃，所以得到3^(a-1) * 4；
- 當(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é)果
