Sword finger offer14 the easiest way to cut rope

Analyzing the topic, we found , stay n<4 When , The maximum product is n-1（ You have to cut ）, be equal to 4 Cut into 2 Equal division , The product is 2, But more than 4 When , We can find out , Cut into several pieces with length of three , remainder <=4 Multiple line segments of , The bigger the product （ Because as long as it is greater than 4, Just cut it into pieces with one 3 The length must be larger than the product of other tangents , such as 5 Cut into pieces 2 3,6 Cut into pieces 3 3） such as 10 We are divided into 3 3 4, The product is 36,17 Cut into pieces 3 3 3 3 3 2 The product of 3^5*2. According to this principle We can easily make a while Cycle to achieve

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;
    }
}

meanwhile 15 Cutting rope II of the question is to add a remainder operation on this basis

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);
    }
}