剪绳子

@author: sdubrz @date: 7/2/2020 3:46:36 PM 难度： 中等 考察内容： 动态规划 @e-mail: lwyz521604#163.com 题目来自《剑指offer》 电子工业出版社

给你一根长度为 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

通过次数29,381 提交次数53,858

我的解法

这道题可以用动态规划来解：Java程序实现如下

class Solution { public int cuttingRope(int n) { if(n==2) { return 1; } int[] array = new int[n+1]; array[1] = 1; array[2] = 2; for(int i=3; i<n; i++) { int temp = i; for(int j=1; j<=i/2; j++) { int t = array[j] * array[i-j]; if(t>temp) { temp = t; } } array[i] = temp; } int temp0 = array[1] * array[n-1]; for(int i=2; i<=n/2; i++) { int t = array[i] * array[n-i]; if(temp0<t) { temp0 = t; } } return temp0; } }

在 LeetCode 系统中提交的结果如下所示

执行结果：通过 显示详情 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗：36.2 MB, 在所有 Java 提交中击败了100.00%的用户

剪绳子II

@date: 7/16/2020 3:20:14 PM

现在对题目进行修改，使 n 的取值范围扩大至 2<=n<=1000。这时候就不能再使用动态规划的方法了。这道题可以用贪心的算法来解，规律是尽量分配较多的3。

下面是网友pipi给出的Java实现：

class Solution { public int cuttingRope(int n) { if(n == 2) return 1; if(n == 3) return 2; long res = 1; while(n > 4){ res *= 3; res = res % 1000000007; n -= 3; } return (int)(res * n % 1000000007); } }

在 LeetCode 系统中提交的结果为

执行结果：通过 显示详情 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗：36.4 MB, 在所有 Java 提交中击败了100.00%的用户

这道题，真正在应试过程中从正面推导出做法可能比较困难，或许网友KAI给出的这种暴力找规律的思路更实用一点，或许可解燃眉之急：

class Solution { public: void dfs(int n, long sum, long multi, long& ans) { if (sum == n) { ans = max(ans, multi); return; } else if (sum > n) { return; } for (long i = 1; i < n; i++) { dfs(n, i+sum, i*multi, ans); } return; } int cuttingRope(int n) { long ans = 0; dfs(n, 0, 1, ans); return ans; } }; //---> 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