剑指 Offer 14- I. 剪绳子

剑指 Offer 14- I. 剪绳子

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

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

• 2 <= n <= 58

解题思路：

https://www.acwing.com/video/149/

结论: 长度为length的绳子可以分成若干个3和2 证明:(题目中绳子长度n >= 2, 段数m >= 2) 1、若ni >= 5时, 3 * (ni - 3) >= ni, 3 * ni - 9 >= ni, 2 * ni >= 9成立,说明每段中长度ni不存在是5; 2、若ni = 4时, 4 == 2 * 2,说明当ni存在为4时,可以分成2个2; 3、2 * 2 * 2 < 3 * 3,说明最多只能存在两个2,如果存在3个2,可以分成2个3,这样乘积更大;  

 1 /*
 2 *   解题思路:
 3 *   结论: 长度为length的绳子可以分成若干个3和2
 4 *   证明:(题目中绳子长度n >= 2, 段数m >= 2)
 5 *   1、若ni >= 5时, 3 * (ni - 3) >= ni, 3 * ni - 9 >= ni, 2 * ni >= 9成立,说明每段中长度ni不存在是5;
 6 *   2、若ni = 4时, 4 == 2 * 2,说明当ni存在为4时,可以分成2个2;
 7 *   3、2 * 2 * 2 < 3 * 3,说明最多只能存在两个2,如果存在3个2,可以分成2个3,这样乘积更大;
 8 */
 9 class Solution {
10 public:
11     int cuttingRope(int n) {
12         if (n <= 3) {
13             return 1 * (n - 1);
14         }
15         int ans = 1;
16         // 可以含有2个2
17         if (n % 3 == 1) {
18             ans *= 4;
19             n -= 4;
20         }
21         // 仅含有1个2
22         if (n % 3 == 2) {
23             ans *= 2;
24             n -= 2;
25         }
26         // 分成若干个3
27         while (n > 0) {
28             ans *= 3;
29             n -= 3;
30         }
31         return ans;
32     }
33 };