> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/dynamic-programming/cut-rope.md).

# 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