题目
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1）,求最大乘积
https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
解法
递归+记忆化存储
方法一：分治 思想， 采用递归， 最大F(n)可以F(n-1)求得，一直递推至F(2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int cuttingRope(int n) {
int[] memo = new int[n+1];
return memorize(n, memo);
}
private int memorize(int n, int[] memo) {
if (n ==2) {
return 1;
}
if (memo[n] != 0) {
return memo[n];
}
int res = -1;
for (int i=1; i<n; i++) {
res = Math.max(res, Math.max(i*(n-i), i*memorize(n-i, memo)));
}
memo[n] = res;
return memo[n];
}
}
|
数学公式
方法二：数学公式
由算术几何均值不等式
推论一： 将绳子 以相等的长度等分为多段 ，得到的乘积最大。
推论二： 尽可能将绳子以长度 3等分为多段时，乘积最大。
切分规则：
最优： 3 。把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0,1,2三种情况。
次优： 2。若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。
最差： 1。若最后一段绳子长度为 1；则应把一份 3 + 1替换为 2 + 2，因为22 >31。
1
2
3
4
5
6
7
8
9
| class Solution {
public int cuttingRope(int n) {
if(n <= 3) return n - 1;
int a = n / 3, b = n % 3;
if(b == 0) return (int)Math.pow(3, a);
if(b == 1) return (int)Math.pow(3, a - 1) * 4;
return (int)Math.pow(3, a) * 2;
}
}
|
贪心
分治想法， 每一步最优，推论得出 方法二
动态规划（自底向上）
同样地，我们也可以使用动态规划，从已知值 F(2)逐步迭代到目标值 F(n)，它是一种自底向上的方法。
当绳子长度n>3时，最后一段绳子长度只有2，3两种情况(证明参考高赞精选贴)，因此：
dp[i] = max { 2 dp[i-2], 3 dp[i-3] }
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int cuttingRope(int n) {
if(n<=3) return n-1;
int[] dp = new int[n+1];
dp[2] = 2; dp[3] = 3;
for(int i = 4; i <= n; i++){
dp[i] = 2 * dp[i-2] > 3 * dp[i-3] ? 2 * dp[i-2] : 3 * dp[i-3];
}
return dp[n];
}
}
|
