剑指 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:

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

示例 2:

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

提示: 2 <= n <= 58

链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof

题解

这道题目完全是脑筋急转弯, 可以发现大于 4 的长度只要每次切割出 3 然后递归.

如果切割出 <=4 的长度就不再继续切了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
n     乘积     子数字
2 1 1 1
3 2 1 2
4 4 2 2
5 6 2 3
6 9 3 3
7 12 2 2 3
8 18 2 3 3
9 27 3 3 3
10 36 2 2 3 3
11 54 2 3 3 3
12 81 3 3 3 3
13 108 2 2 3 3 3
14 162 2 3 3 3 3
15 243 3 3 3 3 3
16 324 2 2 3 3 3 3
17 486 2 3 3 3 3 3
18 729 3 3 3 3 3 3
19 972 2 2 3 3 3 3 3
20 1458 2 3 3 3 3 3 3
21 2187 3 3 3 3 3 3 3
22 2916 2 2 3 3 3 3 3 3
23 4374 2 3 3 3 3 3 3 3
24 6561 3 3 3 3 3 3 3 3
25 8748 2 2 3 3 3 3 3 3 3
26 13122 2 3 3 3 3 3 3 3 3
27 19683 3 3 3 3 3 3 3 3 3
28 26244 2 2 3 3 3 3 3 3 3 3
29 39366 2 3 3 3 3 3 3 3 3 3
1
2
3
4
5
var cuttingRope = function(n, x) {
const map = x ? [1, 2, 3, 4] : [0, 1, 2, 4];
if (n <= 4) return map[n - 1];
return Math.max(3 * cuttingRope(n - 3, true));
};