[数据结构与算法]剑指offer14-剪绳子 最简单方法

分析题目我们发现，在n<4的时候，最大乘积都是n-1（必须切一刀），等于4的时候切成2等分，乘积为2，但是大于4的时候，我们可以发现，切成多个长度为三，余数<=4的多个线段，乘积越大（因为只要大于4，只要切成带有一个3长度的一定比其他切法乘积大，比如5切成2 3，6切成3 3）比如 10我们分成3 3 4，乘积为36，17切成 3 3 3 3 3 2 乘积3^5*2。根据这个原理 我们很容易可以做个while循环实现

class Solution {
    public int cuttingRope(int n) {
        if(n < 4){
            return n - 1;
        }
        int res = 1;
        while(n > 4){
            res *= 3;
            n -= 3;
            //
        }
        return res * n;
    }
}

同时15题的剪绳子二也就是在这个基础上加上一个取余操作

class Solution {
    public int cuttingRope(int n) {
            if(n<4){
                return n-1;
            }long total=1;
            while(n>4){
                total*=3;
                total=total%1000000007;
                n-=3;
            }
            return (int )(total*n%1000000007);
    }
}