https://blog.csdn.net/Y_Mlsy/article/details/107357681
这个证明非常清晰

确实不错,谢谢你

给一个快速幂的写法，时间复杂度O(logn)

class Solution {
public:
    int fp(int n,int m){
        return m==0?1:(m&1?fp(n*n,m>>1)*n:fp(n*n,m>>1));
    }
    int maxProductAfterCutting(int length) {
        return length<=3?length-1:(length%3?(length%3==2?2*fp(3,length/3):4*fp(3,length/3-1)):fp(3,length/3));
    }
};

依次把length除以从2到length得到a，同时取模得到b，那么最大值一定是pow(a,i-b)pow(a+1,b)。因为被分开的数越接近值越大，（类似于相同长度下正方形大于长方形）
/
2023.3.15
/
class Solution {
public:
int maxProductAfterCutting(int length) {
int ans=0;
for(int i=2;i<=length;i++){
int a=length/i;
int b=length%i;
int tmp=pow(a,i-b)pow(a+1,b);
if(tmp>ans) ans=tmp;

    }
    return ans;
}

};

时间复杂度O（n）

/
2023.3.15
/
class Solution {
public:
int maxProductAfterCutting(int length) {
if (length <= 3)return length - 1;
int a = length / 3;
int b = length % 3;
switch (b){
case 0:
return pow(3, a);
case 1:
return pow(3, a - 1) * 4;
case 2:
return pow(3, a ) * 2;
}
}
};

当然，在证明了关于m的问题之后，我们就可以着手调整m了，这部分的内容也很简单，可以参考y神的过程。本质上还是经过有限次数的局部调整。

经过有限次数，不断调整到最优状态，在高联里面还是挺常见的。
实际上，如果将m也纳入考虑，即考虑长度n的绳子被分为m份，那么这是一个非常经典的小问题。
只需要：对于任意一个序列，我们每次都选取一对数，一个大于序列平均数，另一个小于序列平均数。对这两个数向着这两个数的均值进行调整。
这样的过程保证新的序列乘积大于原乘积，同时这种调整是有限多次的。
我们能够保证这样最后的结果是最优，且能够达到。只需要尽可能的取平均值，而后，整数带来的剩余平均的分布在尽可能多的数上。
转眼大学已经上了三年了。高中的事情已经过去了好久。所幸在个人的小小历史尘埃里，我曾经有过一些美好的回忆。至少就某种程度而言，我还算幸运。

秀

牛

快速幂：那我走~

int maxProductAfterCutting(int length) {
int a=length%3;
int b=length/3;
int ans=1;
if(length>=5)
{
if(a==0)
{
for(int i=1;i<=b;i++)
{
ans*=3;
}
return ans;
}
else if(a==1)
{
for(int i=1;i[HTML_REMOVED]=2)
{
if(length==2)
return 1;
else if(length==3)
{
return 2;
}
else
{
return 4;
}
}
}

y总6行，却用了我毕生的知识

而我两行O(logn)（
行数最少1行直接return，但是要用pow就会变成double导致精度丢失（

class Solution {
public:
int maxProductAfterCutting(int length) {
if(length <= 3) return length - 1;
int k,x;
k = length % 3;
x = length / 3;
if(k == 1) return pow(3,x - 1) * 4 ;
else if(k == 2) return pow(3,x) * 2;
else if(k == 0) return pow(3,x);
}
};
请问y总这样的时间复杂度是多少呀

import math
class Solution(object):
    def maxProductAfterCutting(self,length):#DP
        """
        :type length: int
        :rtype: int
        """
        dp=[1]*(length+1)
        for i in range(2,length+1):#dp[i]表示长度为i的绳子剪成m段后的最大乘积
            for j in range(2,i//2+1):#(2,i)or(2,i//2+1)都行
                dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]))
        return dp[length]

测试案例有缺情况哦，这个代码ac了，但是很明显3的话是不对的。

为什么当(n % 3 == 2)的时候，是用res来乘2？

此时分解的结果是一个2和一堆3，所以先将res置成2，然后再乘上那堆3即可。

这证法属实离谱，

这种证法在数学竞赛中比较常见的。

我感觉这种证法有点没法说服我 网上那种不等式证法我能接受

这样证下来是可以说明问题 但是为什么会这样想呢 感觉有一种配凑出来的味道- -让我凑我是凑不出来

当你下次见到类似的证法时就会感觉熟悉了hh 不过证明方式选择一种自己最习惯的即可。

这是数学归纳法呀

上面的证明不是数学归纳法，不过可以改造成数学归纳法的形式。

所以Y总的证明方法的名称叫啥hhh

好像没有名字。

y总，我在奥数课上也学了这种证法，挺容易懂的

感觉数学功底好重要啊

数学毕竟是基础学科嘛

看到了一个比较通俗的解释：https://blog.csdn.net/Koala_Tree/article/details/78932316
当n<5时，我们会发现，无论怎么剪切，乘积product <= n，n为4时，product最大为2*2=4；
当n>=5时，可以证明2(n-2)>n并且3(n-3)>n。而且3(n-3)>=2(n-2)。所以我们应该尽可能地多剪长度为3的绳子段。

不错

感觉这个这个证明有些牵强

这个证明的思路是这样的：证明了最优解中一定可以只包含2和3，且2的个数小于等于2。感觉没啥问题hh

证明思路是没问题的，只是写的精简了一些而已。先排除掉2,3以外的因数，然后确定2的个数小于等于2。分别讨论2的个数为0,1,2，为0则n%3==0，全是3；为1，则仅有两种可能，把一个3+1变成2+2或者3+1，知道不能有1（或者说31<22）故将一个3+1变成两个2,；为2，则有且仅有这一个二。综上，代码如下：
if (n % 3 == 1) res = 4, n -= 4;
else if (n % 3 == 2) res = 2, n -= 2;
while (n) res *= 3, n -= 3;

不错。

👍

清晰

如果把证明过程放在这 更不明白了 大概的说一下听明白了得了