[jzof] 14 cut rope

Recurrence of violence ：

    //  Method 1,  Recurrence of violence ,  The time complexity is O(n!), The space complexity is O(n), At most n paragraph , The length of each segment is 1, The recursion depth is n
    public static int cutRope(int target) {
    
        if (target == 2) {
    
            return 1;
        } else if (target == 3) {
    
            return 2;
        } else {
    
            return backTrack(target);
        }
    }

    private static int backTrack(int n) {
    
        // n<=4, Indicates that there is no division , The length is the longest .
        if (n <= 4) {
    
            return n;
        }
        int res = 0;
        for (int i = 1; i < n; i++) {
    
            res += Math.max(res, i * backTrack(n - i));
        }
        return res;
    }

Memory recursion ：

    //  Memory recursion , The time complexity is O(n^2), The space complexity is O(n)
    static int[] mark = null;
    public static int cutRope2(int target) {
    
        if (target == 2) {
    
            return 1;
        } else if (target == 3) {
    
            return 2;
        }
        //  Create an array , The initial value is 0
        mark = new int[target+1];
        return backTrack2(target);
    }

    private static int backTrack2(int target) {
    
        if (target <= 4) {
    
            return target;
        }
        if (mark[target] != 0) {
    
            return mark[target];
        }
        int ret = 0;
        for (int i = 1; i < target; i++) {
    
            ret = Math.max(ret, i * backTrack2(target - i));
        }
        return mark[target] = ret;
    }

Dynamic programming ：

    //  Dynamic programming ,  The time complexity is O(n^2), The space complexity is O(n)
    public static int cutRope3(int target) {
    
        if (target == 2) {
    
            return 1;
        } else if (target == 3) {
    
            return 2;
        }
        int[] mark = new int[target + 1];
        for (int i = 1; i <= 4; i++) {
    
            mark[i] = i;
        }
        for (int i = 5; i <= target; i++) {
    
            for (int j = 1; j < i; j++) {
    
                mark[i] = Math.max(mark[i], j * mark[i - j]);
            }
        }
        return mark[target];
    }

Reference article ：
https://blog.csdn.net/arpospf/article/details/110492761