ACWING25. 剪绳子（剑指offer，数学/dp）

本文主要是介绍ACWING25. 剪绳子（剑指offer，数学/dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，2≤n≤58 并且 m≥2）。

每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少？

例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。

样例
输入：8

输出：18

思路：

1. 直观的思路是在确定分了多少段的前提下，分的越平均越好。这不难理解，假设分平均以后是a,a，那么打破平均变成a+1,a-1，乘积变成了a²- 1，反而变小了

class Solution {
public:int maxProductAfterCutting(int length) {int ans = 0;for(int i = 2;i <= length;i++) {int num = 1;int a = length / i;int b = length % i;for(int j = 1;j <= b;j++) num *= a + 1;for(int j = 1;j <= i - b;j++) num *= a;ans = max(ans,num);}return ans;}
};

2. 还可以利用动态规划，定义dp[i]代表长度为i的时候分出来的最大成绩。可以得到
   $dp[i]=max(dp[i],dp[i-j]\ast j)$，
   但是注意每一个绳子至少分两段，这意味着dp[i - j]至少分了两段，但或许 i - j 这个长度的绳子不分反而更优。所以
   $dp[i]=max((i-j)\ast j,dp[i-j]\ast j,dp[i])$

class Solution {
public:int dp[105];int maxProductAfterCutting(int length) {memset(dp,0,sizeof(dp));dp[1] = 1;for(int i = 2;i <= length;i++) {for(int j = 1;j < i;j++) dp[i] = max((i - j) * j,max(dp[i],dp[i - j] * j));}return dp[length];}
};

上述两种方法都包含了两个循环，是n方级别的算法。是否存在更高效的算法呢？这就是接下来介绍的数学方法。

一个已知的结论是：所有大于3的数，都可以由2和3组成，如4 = 2 + 2，5 = 2 + 3，那么答案与2和3有关呢？

假设对于 $n\ge 4$
当$n=4$时，枚举得到$n=2+2$时，结果最优，为4.
当$n>4$时
将n拆出一个2得到$n=n-2+2$,
那么 $2\ast (n-2)=2n-4=n+(n-4)>n$
对于3同理：$3\ast (n-3)=n+2n-9>n$

而假设将n拆出一个数k
且$k>3$
那么乘积为$k\ast (n-k)$

我们知道，k可以拆成2和3的倍数和，而没拆一次，都会使得新产生两个数的乘积大于k。

所以可以将k拆成 $k=k-3+3,k=k-2+2。$
结果为$(k-3)\ast 3\ast (n-k)$
或者$(k-2)\ast 2(n-k)$
对于$k-3,k-2$以及$n-k$,因为也能拆成2和3，所以也能应用同样的结论：n拆成2和3，乘积最大。

但是注意到当$3\ast 3>2\ast 2\ast 2$，当n≥6的时候，尽量拆出3最优。

综合以上，
如果n%2 = 1，先将4提取出来（4要拆成2），res = 4
如果n%2 = 2，先提取一个2出来（这个2拆不了），res = 2。
剩下的部分全部拆成3，复杂度为O(n)。

如果再利用快速幂，复杂度可以进一步优化为O(logn)

class Solution {
public:int qpow(int n,int m) {int res = 1;while(m) {if(m & 1) res = res * n;n = n * n;m >>= 1;}return res;}int maxProductAfterCutting(int n) {if(n <= 3) return (n - 1);int res = 1;if(n % 3 == 1) n -= 4,res = 4;else if(n % 3 == 2)  n -= 2,res = 2;res *= qpow(3,n / 3);return res;}
};

这篇关于ACWING25. 剪绳子（剑指offer，数学/dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---