打卡

剑指14-1:
剪绳子。
两种解法：
1.数学法，利用算术均值不等式将计算过程转变为求x^(1/x)的最大值，进行数学推导可以得到极值点是e，接近的是2，3。计算得到x取3时候函数最大，因此将整个数尽量拆成3，假设最后余1，可以组成2*2
假设最后余2，不动。对于<=3的情况再做一步处理

int pow(int n){
        int res =1;
        while(n--){
            res*=3;
        }
        return res;
    }
    int cuttingRope_1(int n) {
        if(n<3)return n-1;
        int div = n/3;
        int mod = n%3;
        if(mod==0)return pow(div);
        if(mod==1)return pow(div-1)*4;
        return pow(div)*2;
    }

2.动态规划
dp[i]表示长度为i的绳子可以组成的最大乘积，
遍历[1,i）
dp[i] = max(dp[i],j*max(dp[i-j],i-j))

    int cuttingRope(int n){
        vector<int> dp(n+1);
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3;i<=n;i++){
            for(int j = 1;j<i;j++){
                dp[i] = max(dp[i],j*max(dp[i-j],i-j));
            }
        }  
        return dp[n];
    }

3.大数取余的溢出问题：

class Solution {
public:
    int cuttingRope(int n) {
        if(n<=3) return n-1;
        int a = n/3, b = n%3;
        int mod = 1e9+7;
        if(b==0) return pow1(3,a,mod,1);
        if(b==1) return pow1(3,a-1,mod,4);
        return pow1(3,a,mod,2);
    }

    long long quick_pow(long long a,long long n,long long mod,int mul){
        long long res = 1;
        while(n > 0){
            if(n&1)
                res = (res * a)%mod;
            a = (a * a)%mod;
            n >>= 1;
        }
        res = (res*mul)%mod;
        return (int)(res);
    }
};