# 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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://llssff.gitbook.io/coding-problems/dynamic-programming/cut-rope.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.