CN-14. Cutting Rope

tags: Dynamic Programming, Greedy, Fast Modular Exponentiation
source: leetcode-cn

Edge Cases

Solution 1 - DP, when number is small

For a rope with length i, we can cut by j and i - j, for every part, we can cut or not cut, so: dp[i] = Max(dp[j], j) * Max(dp[i-j], i-j) for all j

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], Math.max(j, dp[j]) * Math.max(i - j, dp[i - j]));
            }
        }

        return dp[n];
    }
}

Complexity

time: O(N^2)
space: O(Nn)

Solution 2 - Greedy

Image what lengths will be left after cutting and get a maximum product:

1: possible
2: possible
3: possible, because cuttign rope with length 3 will get smaller product than 3
4: possible, it’s 2 and 2 cut, 2 * 2 > 1 * 3
= 5: not possible, cutting always have larger product

so, we need to get length 3 cut as much as possible when length > 4, because when 4, 2-2 cut will be better

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

Complexity

time: O(N)
space: O(1)

Solution 3 - FME

class Solution {

    private int mod = (int)1e9 + 7;

    public int cuttingRope(int n) {
        if(n < 4){
            return n-1;
        }
        int cnt3 = n / 3;
        if(n % 3 == 0){
            return (int)pow(3, cnt3);
        } else if(n % 3 == 1){
            return (int)((pow(3, cnt3 - 1) * 4) % mod);
        } else {
            return (int)((pow(3, cnt3) * 2) % mod);
        }
    }

    private long pow(long base, int num){
        long res = 1;
        while(num > 0){
            if((num & 1) == 1){
                res *= base;
                res %= mod;
            }
            base *= base;
            base %= mod;
            num >>= 1;
        }
        return res;
    }
}