Cut Rope

Given a rope length n, find the max product between possible rope cuts.

There need to be at least one cut.

Solution: DP with value array

Base Case: 0 and 1 length cannot be cut, thus = 0

Inductive rule:

For each possible cut:
    left side: check if there exists an optimal cut, or is no cut better
    right side: Keep whole as its cuts will be explored later
    
    Check if left * right generates a better cut than previously know
    update current if true

Slowly grow the rope to length n

At each length of rope, check every possible cut.

Case 1: No cut is best cut

Case 2: Cut here into two segments

Case 3: Cut m times up to here, check for n with prev steps

Update max amongst all three cases.

Update max amongst all cuts at current length

Return bestCuts[n]

Implementation:

public int cutRope(int n){
    if (n < 2) return 0;
    int[] bestCuts = new int[n + 1];
    bestCuts[0] = 0;
    bestCuts[1] = 0;
    
    for (int i = 2; i <= n ; i++){
        int curMax = 0;
        for (int j = 1; j < i ; j++){
            curMax = Math.max(curMax, Math.max(bestCuts[j], j) * (i - j));
        }
        curMax[i] = curMax;
    }
    
    return bestCuts[n];
}

TC: O(N^2) double for loop through 1 -> N

SC: O(N) memoize array