🔗：https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/

剪绳子二和一看上去是一个问题，只是多了取余的操作，我却发现按照一的解法根本不能过。先看看我的剪绳子一的做法：

class Solution {
public:
    int cuttingRope(int n) {
        if(n==2)
            return 1;
        vector<int> dp(n+1);
        dp[1]=1;
        dp[2]=1;
        for(int i=3;i<=n;i++){
            for(int k=1;k<=i-1;k++){
                dp[i]=max(dp[i-k]*k,dp[i]);
                dp[i]=max((i-k)*k, dp[i]);
            }
        }
        return dp[n];
    }
};

我自认为做法还是聪明的，用动态规划并且通过循环避免了重复的计算，唯一需要注意的是，绳子至少要剪一刀，所以存在有的情景一刀不剪比必须剪一刀得到的最大值要最大（比如2）。然而当我将这种做法照搬并只加上取余的操作后只能得到溢出的结果，当我把数据类型改成long long也只能得到解答错误。并且通过最近的一次笔试我也发现，这种很大的数取余是很容易考的，对我而言很容易出错。

通过查看题解以及《剑指Offer》原书的讲解，发现他们的解法都用了我未曾意识到的结论：想要剪绳子得到的乘积最大，在剪的时候要满足两个条件：

1. 绳子尽量剪相等的段
2. 绳子的长度尽量取3

我感觉第一个结论是很容易得到的，类似相同长度正方形面积最大，而第二个结论似乎不是那么显然，但是按照原书的讲解很容易理解。当绳子长度：

• 绳子长度为2时，最大乘积为1（至少剪一刀）
• 绳子长度为3时，最大乘积为2（1$\times$2）
• 绳子长度为4时，最大乘积为4（2$\times$2)
• 绳子长度为5时，最大乘积为6（2$\times$3)

当绳子长度$\geq$5时，$3(n-3)>n$ 并且 $3(n-3)\ge2(n-2)$。所以得到第二个结论。

有了上面的结论，最大乘积就可以直接求，现在唯一的问题就是取余，已知（其实这个式子我也是才知道）：

$(x\cdot y)\odot p= [(x\odot p)(y\odot p)]\odot p$

在取了很多长度为3的段以后，乘积$3^a$一定会溢出，我们怎么保证在计算过程中不溢出并且保证多次乘积取余后的结果正确？参考：面试题14- II. 剪绳子 II（数学推导 / 贪心思想 + 快速幂求余，清晰图解）

1. 循环取余：

   $3^a\odot p=[3^{(a-1)}\odot p\cdot 3]\odot p$

   仔细观察$3^{(a-1)}\odot p\cdot 3$还是有超过p的危险，也就是可能溢出。这个方法对取余是有用的，但在这题上还是需要设为long long。

2. 快速幂取余：

   我们可以很简单地把问题规模缩小一半：

   $x^a\odot p=(x^2)^{a/2}\odot p=(x^2\odot p)^{a/2}\odot p$

   稍微麻烦一点地是需要对a是奇数偶数进行分别讨论，当a是奇数时，

   $x^a\odot p=[(x^2)^{a//2}\cdot x]\odot p=[(x^2\odot p)^{a//2}\cdot x]\odot p)$

​ 实现的时候使用递归逻辑更清楚，相反循环不太好理解，虽然递归多用了一些空间，但是时间复杂度是一样的！！！可以观察一下上述式子中重复出现的子式：$(x^2\odot p)^i$。我们可以写一下前几项：

​ $x^1\odot p=[(x^2\odot p)^0\cdot x]\odot p$

​ $x^2\odot p=(x^2\odot p)^1\odot p$

​ $x^3\odot p=[(x^2\odot p)^1\cdot x]\odot p$

​ 可以看到我们所省的就是循环计算$(x^2\odot p)^i$的次数，只用算一半次数就可以了。

//计算(3^2%p)^x
long long square_pow(int x){
    if(x==0)
        return 1;
    long long tmp=square_pow(x/2);
    if(x%2==0)
        return tmp*tmp%p;
    else
        return tmp*tmp*9%p;
}
long long cube_pow(int i){
    if(i%2==0){
        return square_pow(i/2)%p;
    }
    else{
        return (square_pow(i/2)*3)%p;
    }
}

​ 我对比了一下两个方法，对于这道题而言，执行用时都是0ms，而快速求幂的代码其实不是很好写。相信走通一遍以后，再遇到来写应该会快很多。